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.