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
– Libor, Commented Oct 28, 2022 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
– VLAZ, Commented Oct 28, 2022 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
– Libor, Commented Oct 28, 2022 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
– Peter Seliger, Commented Oct 28, 2022 at 12:07

VLAZ · Accepted Answer · 2023-03-02 17:39:31Z

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 2, 2023 at 17:39

answered Oct 28, 2022 at 12:07

VLAZ

29.6k9 gold badges65 silver badges87 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ben Aston Over a year ago

How would you do the join operation in userland code in O(N) space?

VLAZ Over a year ago

@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).

Carsten Massmann · Accepted Answer · 2022-10-28 12:06:29Z

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, 2022 at 12:06

answered Oct 28, 2022 at 12:04

Carsten Massmann

28.4k3 gold badges25 silver badges49 bronze badges

4 Comments

VLAZ Over a year ago

Which...is still worse than the array option and again takes O(n!) space.

Carsten Massmann Over a year ago

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.

rici Over a year ago

@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.)

VLAZ Over a year ago

@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.

Ben Aston · Accepted Answer · 2022-10-28 13:33:14Z

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, 2022 at 13:33

answered Oct 28, 2022 at 11:55

Ben Aston

56k69 gold badges221 silver badges351 bronze badges

3 Comments

VLAZ Over a year ago

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!)

Ben Aston Over a year ago

It meets the requirement of not using an array...

VLAZ Over a year ago

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

kevinSpaceyIsKeyserSöze · Accepted Answer · 2022-10-28 12:23:54Z

0

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"));

answered Oct 28, 2022 at 12:23

kevinSpaceyIsKeyserSöze

4,4802 gold badges18 silver badges29 bronze badges

Comments

Peter Seliger · Accepted Answer · 2022-10-28 13:32:24Z

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')
);

Collectives™ on Stack Overflow

Reverse a string in JavaScript without using an array

5 Answers 5

2 Comments

4 Comments

3 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

4 Comments

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related