Reverse String
EasyPrompt
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses recursion to swap characters from the outside in. A helper function is defined that takes two pointers, one at the start and one at the end of the current segment to be reversed. In each recursive call, it swaps the characters at these pointers and then calls itself for the inner segment.
Algorithm
- Define a helper function
helper(s, left, right)that takes the character array and two pointers,leftandright. - Set the base case for the recursion: if
leftis greater than or equal toright, it means the segment is fully reversed, so return. - In the recursive step, swap the characters at
s[left]ands[right]. - Make a recursive call for the inner segment of the array:
helper(s, left + 1, right - 1). - Initiate the process from the main function by calling
helper(s, 0, s.length - 1).
Walkthrough
The core idea is to solve the problem by breaking it down into smaller, identical subproblems. We define a function that reverses a segment of the array defined by left and right indices.
The base case for the recursion is when the left pointer has met or surpassed the right pointer. This indicates that the segment is either empty or contains a single character, which doesn't need reversal.
In the recursive step, we swap the characters at the left and right ends of the current segment. Then, we invoke the function again for the sub-array that lies between these two pointers, effectively moving inwards.
class Solution { public void reverseString(char[] s) { helper(s, 0, s.length - 1); } private void helper(char[] s, int left, int right) { if (left >= right) { return; } char temp = s[left]; s[left] = s[right]; s[right] = temp; helper(s, left + 1, right - 1); }}Complexity
Time
O(N), where N is the length of the character array. The function makes N/2 recursive calls before reaching the base case, and each call performs a constant amount of work (one swap).
Space
O(N), where N is the length of the string. The space complexity is determined by the depth of the recursion stack. For a string of length N, the recursion depth will be approximately N/2, leading to O(N) space usage. This does not meet the problem's constraint of O(1) extra memory.
Trade-offs
Pros
The code can be very elegant and concise.
It's a good way to demonstrate an understanding of the divide-and-conquer paradigm.
Cons
Violates the O(1) extra space constraint due to the memory used by the recursion stack.
Can lead to a
StackOverflowErrorfor very large input strings.
This is the optimal, in-place approach that satisfies all the problem constraints. It uses two pointers, one starting from the beginning of the array (left) and the other from the end (right). The pointers move towards each other, and at each step, the characters they point to are swapped.
Algorithm
- Initialize two pointers:
leftat the beginning of the array (index0) andrightat the end of the array (indexs.length - 1). - Use a
whileloop that continues as long asleft < right. - Inside the loop, swap the characters at the
leftandrightpointers using a temporary variable. - After the swap, move the pointers towards the center by incrementing
leftand decrementingright. - The loop terminates when the pointers meet or cross, at which point the array is fully reversed.
Walkthrough
This iterative method is the standard way to solve this problem while adhering to the memory constraint. We set up two pointers, left starting at index 0 and right at the last index. We then loop until the left pointer is no longer less than the right pointer. In each iteration, we swap the characters s[left] and s[right]. After the swap, we move left one step to the right and right one step to the left, bringing them closer to the middle. This process continues until the entire array is reversed. The loop condition left < right correctly handles both even and odd length arrays, ensuring the middle element (in odd-length arrays) is not moved.
class Solution { public void reverseString(char[] s) { int left = 0; int right = s.length - 1; while (left < right) { // Swap characters char temp = s[left]; s[left] = s[right]; s[right] = temp; // Move pointers towards the center left++; right--; } }}Complexity
Time
O(N), where N is the length of the character array. We iterate through approximately N/2 elements of the array to perform the swaps. This results in a linear time complexity.
Space
O(1). We only use a few variables (`left`, `right`, `temp`) to store pointers and for the swap. The amount of extra memory used is constant and does not depend on the size of the input array. This meets the problem's constraint.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1), satisfying the in-place requirement.
Simple and easy to understand and implement.
Avoids any risk of stack overflow, making it safe for very large inputs.
Cons
There are no significant cons for this approach as it is the most efficient and standard solution for this problem.
Solutions
Solution
class Solution {public: void reverseString(vector<char> &s) { for (int i = 0, j = s.size() - 1; i < j;) { swap(s[i++], s[j--]); } }};class Solution {public void reverseString(char[] s) { for (int i = 0, j = s.length - 1; i < j; ++i, --j) { char t = s[i]; s[i] = s[j]; s[j] = t; } }}/** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */ var reverseString = function (s) { for (let i = 0, j = s.length - 1; i < j; ++i, --j) { [s[i], s[j]] = [s[j], s[i]]; } };class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ s[:] = s[:: - 1] # class Solution : def reverseString ( self , s : List [ str ]) -> None : i , j = 0 , len ( s ) - 1 while i < j : s [ i ], s [ j ] = s [ j ], s [ i ] i , j = i + 1 , j - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.