Reverse a string in JavaScript without using an array

Question

A simple way of reversing a string is as below:

const test = 'hello';

let i = 0;
let j = test.length - 1;

while (i < j) {
    let temp = test[i];
    test[j] = test[i];
    test[i] = temp;
    i++;
    j--;
}
console.log(test);

If we try to access string using an index it works fine. For example console.log(test[2]) returns 'l'

But reversing a string using the method above returns unchanged string 'hello'. We need to use an array, reverse it and then join it to return the reversed string. But in that case we will be using an extra space. Can we do it without using an extra space?

Technically, you will need some extra space anyway, as JavaScript string are immutable primitives. — Libor, Oct 28 '22 at 11:53
@savageGoat why do you show this code? Yes, it supports what Libor says but it's weird to spring it without explanation. Or real need, either. — VLAZ, Oct 28 '22 at 11:57
@savageGoat I would consider splitting as "using extra space", because it creates array (kind of). But my comment was just meaned to mention than in some languages you can modify string in place, without arrays, new references etc. I am not sure what "extra space" means in this question, may it be "we need one-liner", "no other variables" or "least space in memory". — Libor, Oct 28 '22 at 12:06
The entire approach fails anyhow due to not being allowed changing characters in place within a string value (and this is what the OP's approach tries to accomplish). — Peter Seliger, Oct 28 '22 at 12:07
@Libor "*t creates array (kind of)*" no "kind of" about it. Splitting creates an array. `.join("")` then *also* creates a string. — VLAZ, Oct 28 '22 at 12:09
@VLAZ good point! I checked MDN and "divides a String into an ordered _list_ of substrings" lead me the the wrong way. I was a bit lazy to check if it is array or some iterable object. — Libor, Oct 28 '22 at 12:25

VLAZ · Answer 1 · 2023-03-02T17:39:31.383

2

Strings are immutable in JavaScript. Therefore, they cannot be changed in-place. Any new string requires a new memory allocation, even when doing something as simple as

const str1 = "hello";
const str2 = str[0];

Leaves two strings in memory: "hello" and "h".

Since any attempt to produce a string will create at least one new string, it is therefore impossible to reverse a string without allocating space for a new string where the characters are reversed.

The minimum space complexity for this task is thusO(n) - scales linearly with the string length. Creating an array which can be rearranged in-place and then combined back to the reversed string fulfils this.

edited Mar 02 '23 at 17:39

answered Oct 28 '22 at 12:07

VLAZ

26,331
9
49
67

Thanks for the more in-depth explanation. – Peter Seliger Oct 28 '22 at 12:09
How would you do the join operation in userland code in `O(N)` space? – Ben Aston Oct 28 '22 at 12:11
@BenAston in userland - it won't be. In the native implementation of `.join()` - I've yet to see any evidence it's not `O(n)`. – VLAZ Oct 28 '22 at 12:13

Ben Aston · Answer 2 · 2022-10-28T13:33:14.430

1

The final line of your question means that the answer is "no". We cannot do this without using extra space [in userland JS].

We could, however, do this if we relied on a function written in a systems programming language. And this is the C code used by V8 for Array#join. In such a language the binary representation of the reversed string could be constructed step by step and simply cast to be a UTF-16 string in the final step. I presume this approximates what Array#join does under the hood.

If your requirement is simply to avoid using an array, the following simply successively pulls the code units from the end of the input string and builds a new string from them.

This will fail horribly with surrogate pairs (eg emoji) and grapheme clusters.

const reverse = (s) => {
  let result = ''
  for(let x = s.length-1; x >= 0; x--) {
    result += s[x]
  }
  return result
}

console.log(reverse('hello'))

edited Oct 28 '22 at 13:33

answered Oct 28 '22 at 11:55

Ben Aston

53,718
65
205
331

1

How is that "without extra space"? It's even worse than the linear space that an array would take up, since it's `O(n!)` – VLAZ Oct 28 '22 at 11:56
It meets the requirement of not using an array... – Ben Aston Oct 28 '22 at 11:57
2

"*Can we do it without using an extra space.*" – VLAZ Oct 28 '22 at 11:58

Carsten Massmann · Answer 3 · 2022-10-28T12:06:29.473

1

Here is a recursive way of doing it:

const rev = s => s.length>1 ? s.at(-1)+rev(s.slice(0,-1)) : s;

console.log(rev("This is a test string."))

edited Oct 28 '22 at 12:06

answered Oct 28 '22 at 12:04

Carsten Massmann

26,510
2
22
43

1

Which...is still worse than the array option and again takes `O(n!)` space. – VLAZ Oct 28 '22 at 12:05
Hey @VLAZ, "You can't make an omelette without breaking eggs" ;-) - so we will need some "space" to at least temporarily hold the intermediate results. Let Ashy Ashcsi decide whether this solution is helpful to them or not. – Carsten Massmann Oct 28 '22 at 12:11
1

@VLAZ: Where do you get n! from? n! is the *product* of the integers from 1 to n, but the space used is, at worst, the *sum* of the sizes of the intermediate strings, which is O(n²), a much smaller number. (In practice, it will be probably actually be O(n), because Javascript doesn't always need to copy a string to get a slice, and it can recycle strings when they are no longer referenced. But those are implementation details.) – rici Oct 29 '22 at 04:20
@rici oops, you're right - it's `O(n^2)` my bad. Whether or not the intermediate strings would be there is an implementation detail. There might be an optimisation that removes them, yet I don't think the recursive implementation with `s.slice(0,-1)` will be optimised. I don't think any JS engine will optimise away the new strings created for each recursive call. And if an engine *does* that's again an implementation detail that shouldn't be relied on. – VLAZ Oct 29 '22 at 06:56

Peter Seliger · Answer 4 · 2022-10-28T13:32:24.773

OP

"Can we do it without using an extra space."

nope.

Anyhow ... the OP's while based approached which this time does not try to change characters in place but programmatically a) removes character by character from the input value while b) concatenating the reversed result string ...

function reverseStringWithoutHelpOfArray(value) {
  value = String(value);                          // let i = 0;
  let result = '';                                // let j = test.length - 1;
                                                  // while (i < j) {
  while (value) {                                 //   let temp = test[i];
    result = result + value.slice(-1);            //   test[j] = test[i]; 
    value = value.substring(0, value.length - 1); //   test[i] = temp;
  }                                               //   i++; j--;
  return result;                                  // }
}

console.log(
  reverseStringWithoutHelpOfArray('hallo')
);

score 0 · Answer 5 · answered Oct 28 '22 at 12:23

What about a hacky for loop?

const rev = (str) => {
  for(var i = str.length - 1; i >= 0; i--) {
    str += str[i];
  }
  return str.slice(str.length / 2, str.length);
}

console.log(rev("t"));
console.log(rev("te"));
console.log(rev("tes"));
console.log(rev("test"));

Reverse a string in JavaScript without using an array

5 Answers5