Problem overview
The method reverse receives a string, input, and returns a new string with the same characters in the opposite order. For "hello" it returns "olleh". The statement allows O(n) time and O(n) extra space.
Approach: copy into an array, then swap the ends
The obvious plan is to rearrange the characters in place, but TypeScript strings are immutable. You can read input[0], but writing to it is not allowed, and the compiler reports an error if you try. So the work happens in an array of characters, which can be changed, and the array is turned back into a string at the end.
The array is reversed with two pointers. One starts at the first position and the other at the last. Swap the two characters they point to, move the pointers one step toward each other, and repeat until they meet. Each swap puts two characters in their final places.
For "hello", the array starts as ['h', 'e', 'l', 'l', 'o']:
left = 0, right = 4: swap 'h' and 'o' -> o e l l h
left = 1, right = 3: swap 'e' and 'l' -> o l l e h
left = 2, right = 2: the pointers met, stop
Joined back together, the array gives "olleh". The middle character of an odd-length string stays where it is, because it is its own mirror image.
TypeScript offers a one-line shortcut, input.split("").reverse().join(""), where the array method reverse does the swapping. The lesson writes the swapping loop itself, since that two-pointer pattern is the technique the chapter is about, and it carries over to many other problems: palindromes, sorted-array searches and in-place rearrangements. It also shows what a built-in reverse has to do: touch each pair of positions once, working from the outside in.
Step by step
- Split the string into characters.
input.split("")cuts the string at every position, because the separator is the empty string, and returns astring[]. Call itcharArray. - Create the first pointer,
left, at 0. - Create the second pointer,
right, atinput.length - 1, the last index. - Loop while
left < right. When the pointers meet or cross, every pair has been swapped. - Call
this.swap(charArray, left, right). The swap is a method of the class, so it is reached throughthis. The lesson uses the call first and writes the method afterwards. - Declare
swapwith the parametersarr: string[],i: numberandj: number, returningvoid, because it changes the array and gives nothing back. - Write its body as one destructuring assignment,
[arr[i], arr[j]] = [arr[j], arr[i]]. The right side builds a new two-element array with the old values first, and then the left side stores them back in the opposite positions. No temporary variable is needed. - Move the pointers after each swap:
left++andright--. - Return
charArray.join(""). Joining with an empty string puts nothing between the characters.
The solution in TypeScript
class Solution {
swap(arr: string[], i: number, j: number): void {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
reverse(input: string): string {
let charArray: string[] = input.split("");
let left = 0;
let right = input.length - 1;
while (left < right) {
this.swap(charArray, left, right);
left++;
right--;
}
return charArray.join("");
}
}
The TypeScript details worth knowing:
- The array is shared. Arrays are objects, so
swapreceives a reference to the same array, not a copy. Changes made insideswapare visible inreverse, which is whyswapdoesn't have to return anything. - Type annotations are removed.
string[],numberandvoidhelp the compiler and the reader. They are erased when the code compiles to JavaScript. - Characters made of two code units.
split("")cuts at UTF-16 code units. A character such as an emoji takes two, and reversing them would swap the halves and produce broken text. For ordinary letters, as in the examples, there is no problem.
Complexity
Time: O(n). Splitting and joining each visit every character once, and the loop does at most n / 2 swaps of constant cost.
Space: O(n). The array of characters holds one entry per character of the input, and the joined result is another string of the same length. That matches the budget in the statement.
Edge cases and common mistakes
- Empty string.
""splits into an empty array,rightis -1, and the loop doesn't run. The result is"". - One character.
"a"hasleft = right = 0, so nothing is swapped and the result is"a". - Two characters.
"ab"swaps once, withleft = 0andright = 1, and returns"ba". After the swap the pointers cross, so the loop ends. - Using
left <= right. The last pass would swap a character with itself. That is harmless, but it is extra work. - Swapping without a temporary value. Writing
arr[i] = arr[j]; arr[j] = arr[i];loses the originalarr[i]and leaves two equal characters. The destructuring form avoids it, and so does a temporary variable. - Forgetting
join. ReturningcharArraywould be an array, not a string, which doesn't match the declared return type. - Looping over the whole length. If the pointers kept going until
leftreachedinput.length, every pair would be swapped twice and the array would end up in its original order.
Testing
"hello"gives"olleh"."ab"gives"ba"."a"gives"a".""gives"".