JavaScript O(1) space on character array

• Inspired by other O(1) space solutions. As others have mentioned, Strings are immutable in JS, so we have to split the input into an Array of 1 character Strings to do in-place modifications.

``````/**
* Operates on an array of characters in O(N) time, O(1) space.
* @param {string} str
* @returns {string}
*/
function reverseWords(str) {
// This part is not O(1) space, but it's just our integration code with LeetCode.
// Outside this sandbox, we'd ask callers to pass an a character Array instead of a String
// for best performance.
return _reverseWords(str.split('')).join('');
}

function _reverseWords(chars) {
// Reverse the whole string
reverse(chars);

let spaceCount = 0;
let wordCount = 0;
for(let i=0; i<chars.length; i++) {
// Consume spaces
if(chars[i] === ' ') {
spaceCount++;
continue;
}

// Re-reverse a word
let j; // word end index
for(j=i; j<chars.length && chars[j] !== ' '; j++) {}
j -= 1;
reverse(chars, i, j);
wordCount += 1;

// Shift the word left to collapse extra space
shiftLeft(chars, i, j, spaceCount - wordCount + 1);

i=j;
}

// Remove trailing space
while(spaceCount > wordCount - 1) {
spaceCount--;
chars.pop();
}

return chars;
}

// In place reverse, both indicies inclusive
function reverse(chars, lo, hi) {
lo = lo || 0;
if(typeof hi === 'undefined') hi = chars.length - 1;
while(lo < hi){
tmp = chars[lo];
chars[lo] = chars[hi];
chars[hi] = tmp;
lo++; hi--;
}
}

// In place shift, both indicies inclusive
function shiftLeft(chars, start, end, offset) {
for(let k=start-offset; k<=end-offset; k++) {
chars[k] = chars[k+offset];
}