Solution


Approach 1: Stack of Letters

Intuition and Algorithm

Collect the letters of S separately into a stack, so that popping the stack reverses the letters. (Alternatively, we could have collected the letters into an array and reversed the array.)

Then, when writing the characters of S, any time we need a letter, we use the one we have prepared instead.

Complexity Analysis

  • Time Complexity: , where is the length of S.

  • Space Complexity: .


Approach 2: Reverse Pointer

Intuition

Write the characters of S one by one. When we encounter a letter, we want to write the next letter that occurs if we iterated through the string backwards.

So we do just that: keep track of a pointer j that iterates through the string backwards. When we need to write a letter, we use it.

Complexity Analysis

  • Time Complexity: , where is the length of S.

  • Space Complexity: .


Analysis written by: @awice.