Reverse String Solution for Wipro
Company: Wipro · 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.
Key Understanding:
- The input is an array of characters, not a string
- We must modify the array in-place (no extra arrays)
- We can only use O(1) extra memory (constant space)
- The reversal should be done by swapping characters
Examples
Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Explanation:
- Original: ["h","e","l","l","o"]
- After reversal: ["o","l","l","e","h"]
- Visual representation: h e l l o → o l l e h
Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
Explanation:
- Original: ["H","a","n","n","a","h"]
- After reversal: ["h","a","n","n","a","H"]
- Visual representation: H a n n a h → h a n n a H
Example 3:
Input: s = ["a","b","c"]
Output: ["c","b","a"]
Explanation:
- Original: ["a","b","c"]
- After reversal: ["c","b","a"]
- Visual representation: a b c → c b a
Intuition
The key insight is that we can reverse the string by swapping characters from both ends, moving towards the center. This approach works in-place without requiring extra memory.
Core Concept:
- To reverse a string, we need to swap characters at symmetric positions
- Characters at index i should swap with characters at index n-1-i
- We can do this by using two pointers moving towards each other
Why Two Pointers Work:
- Left pointer starts from the beginning (index 0)
- Right pointer starts from the end (index n-1)
- We swap characters at these positions and move pointers inward
- When pointers meet or cross, the string is fully reversed
Approach
Approach 1: Two Pointers (Optimal)
Algorithm:
1. Initialize left pointer at start (index 0)
2. Initialize right pointer at end (index n-1)
3. While left < right:
- Swap characters at left and right positions
- Move left pointer right (increment)
- Move right pointer left (decrement)
Why This Works:
- Each swap puts two characters in their correct final positions
- After n/2 swaps, all characters are in their correct positions
- The algorithm terminates when pointers meet at the center
Complexity Analysis:
- Time: O(n/2) = O(n) - We perform n/2 swaps
- Space: O(1) - Only constant variables needed
Approach 2: Using Extra Array
Algorithm:
1. Create a new array of same size as input
2. Copy characters from end to start of original array
3. Copy back to original array
Why This Works:
- We create a reversed copy in the temporary array
- Then we copy it back to the original array
- This approach is straightforward but uses extra space
Complexity Analysis:
- Time: O(n) - We traverse the array twice
- Space: O(n) - We need an extra array
Approach 3: Recursive Approach
Algorithm:
1. Use recursion to swap characters
2. Base case: when left >= right (pointers meet or cross)
3. Recursive case: swap characters and call recursively with updated pointers
Why This Works:
- Each recursive call handles one swap
- The recursion naturally moves pointers inward
- Base case ensures termination
Complexity Analysis:
- Time: O(n/2) = O(n) - We make n/2 recursive calls
- Space: O(n/2) = O(n) - Due to recursion stack
Dry Run
Let's trace through Example 1: s = ["h","e","l","l","o"]
Two Pointers Approach:
Initial State: left=0, right=4, s = ["h","e","l","l","o"]
Iteration 1:
- left=0, right=4
- Swap s[0]='h' and s[4]='o'
- Result: s = ["o","e","l","l","h"]
- Move: left=1, right=3
Iteration 2:
- left=1, right=3
- Swap s[1]='e' and s[3]='l'
- Result: s = ["o","l","l","e","h"]
- Move: left=2, right=2
Iteration 3:
- left=2, right=2
- Since left >= right, stop
Final Result: s = ["o","l","l","e","h"]
Recursive Approach:
Call 1: reverseHelper(s, 0, 4)
- Swap s[0]='h' and s[4]='o' → s = ["o","e","l","l","h"]
- Call: reverseHelper(s, 1, 3)
Call 2: reverseHelper(s, 1, 3)
- Swap s[1]='e' and s[3]='l' → s = ["o","l","l","e","h"]
- Call: reverseHelper(s, 2, 2)
Call 3: reverseHelper(s, 2, 2)
- Since left >= right, return (base case)
Final Result: s = ["o","l","l","e","h"]
Key Insights
1. In-Place Operation: Two pointers approach is optimal for in-place reversal
2. Symmetric Swapping: Characters at symmetric positions need to be swapped
3. Center Point: For odd-length strings, the center character stays in place
4. Memory Efficiency: Two pointers use only O(1) extra space
5. Iterative vs Recursive: Iterative approach is more space-efficient
Edge Cases
1. Empty String: Array with 0 elements (no operation needed)
2. Single Character: Array with 1 element (no reversal needed)
3. Even Length: All characters get swapped
4. Odd Length: Center character stays in place, others get swapped
5. Palindrome: String reads the same forwards and backwards
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Two Pointers (Optimal)
Time Complexity: O(n) - We traverse half the array
Space Complexity: O(1) - We use only constant extra space
Advantages:
- Most efficient in-place solution
- Constant space usage
- Simple and intuitive
- Works for any string length
Disadvantages:
- Modifies the original array
- Not suitable if you need to preserve the original
Solution 2: Using Extra Array
Time Complexity: O(n) - We traverse the array twice
Space Complexity: O(n) - We need extra array
Advantages:
- Preserves the original array
- Very straightforward implementation
- Easy to understand
Disadvantages:
- Uses extra space
- Less efficient than in-place approach
- Violates the O(1) space constraint
Solution 3: Recursive Approach
Time Complexity: O(n) - We make n/2 recursive calls
Space Complexity: O(n) - Due to recursion stack
Advantages:
- Elegant recursive solution
- Natural problem decomposition
- Easy to understand logic
Disadvantages:
- Uses recursion stack space
- May cause stack overflow for very long strings
- Less efficient than iterative approach