Reverse String Solution for Capgemini
Company: Capgemini · Difficulty: Easy · Topics: String, Two Pointers
Problem Statement
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.
Examples
Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Explanation: The string "hello" is reversed to "olleh".
Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
Explanation: The string "Hannah" is reversed to "hannaH".
Example 3:
Input: s = ["a","b","c"]
Output: ["c","b","a"]
Explanation: The string "abc" is reversed to "cba".
Intuition
The key insight is to use two pointers approach:
1. Start with one pointer at the beginning and another at the end
2. Swap the characters at these positions
3. Move the pointers inward until they meet in the middle
This approach modifies the array in-place without requiring extra memory.
Approach
Approach 1: Two Pointers (Optimal)
1. Initialize left pointer at index 0 and right pointer at index n-1
2. While left < right:
- Swap characters at left and right positions
- Increment left pointer
- Decrement right pointer
3. The string is now reversed in-place
Approach 2: Using Extra Array
1. Create a new array of the same size
2. Copy characters from end to beginning
3. Copy back to original array
Approach 3: Recursive Approach
1. Base case: if left >= right, return
2. Swap characters at left and right positions
3. Recursively call with left+1 and right-1
Dry Run
Let's trace through Example 1: s = ["h","e","l","l","o"]
Two Pointers Approach:
- Initial: left = 0, right = 4
- Swap s[0] and s[4]: ["o","e","l","l","h"]
- left = 1, right = 3
- Swap s[1] and s[3]: ["o","l","l","e","h"]
- left = 2, right = 2
- Since left >= right, stop
- Result: ["o","l","l","e","h"]
Key Insights
1. In-place Modification: No extra memory required
2. Two Pointers: Efficient O(n/2) swaps
3. Symmetry: Characters equidistant from center are swapped
4. Termination: Stop when pointers meet or cross
Edge Cases
1. Empty string: No action needed
2. Single character: No action needed
3. Even length: Pointers meet at middle
4. Odd length: Pointers cross at middle