344. Reverse String
Model: qwen2.5-coder:14b
Topics: Two Pointers,String
FAANG asked: 1
Acceptance rate: 70.7%
Problem Breakdown
The problem requires us to reverse an input string given as an array of characters s. The goal is to modify the input array in-place without allocating extra space for another array. The constraints specify that the length of the string can range from 1 to 10^5, and each character is a printable ASCII character.
Inputs:
- An array of characters
s.
Outputs:
- The same array
smodified in-place to be the reverse of its original order.
Implicit Constraints/Edge Cases:
- If the input array has only one character or is empty, it should remain unchanged.
- The solution must use O(1) extra memory.
Intuition
A brute-force approach would involve creating a new array and copying characters from the original array in reverse order. However, this approach requires additional space proportional to the size of the input array, which violates the problem’s constraint of using O(1) extra memory.
The key insight is to use a two-pointer technique to reverse the string in-place. By initializing one pointer at the beginning (left) and another at the end (right) of the array, we can swap characters between these pointers and move them towards each other until they meet or cross.
Approach
- Initialize Pointers: Set
leftto 0 (start of the array) andrighttolen(s) - 1(end of the array). - Swap Characters: Swap the characters at the
leftandrightpointers. - Move Pointers: Increment
leftby 1 and decrementrightby 1. - Repeat: Continue the process until
leftis greater than or equal toright. - Termination: The array is now reversed in-place.
This approach ensures that we only use a constant amount of extra space, meeting the problem’s constraints.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. Each character is swapped once.
- Space Complexity: O(1). No additional space is used other than a few variables for pointers and temporary storage during swaps.
Solution
def reverseString(s):
left, right = 0, len(s) - 1
while left < right:
# Swap characters at left and right pointers
s[left], s[right] = s[right], s[left]
# Move pointers towards the center
left += 1
right -= 1
# Example usage:
s1 = ["h","e","l","l","o"]
reverseString(s1)
print(s1) # Output: ["o","l","l","e","h"]
s2 = ["H","a","n","n","a","h"]
reverseString(s2)
print(s2) # Output: ["h","a","n","n","a","H"]
Edge Cases Handled
- Single Character: If the input array has only one character, the pointers will not move, and the array remains unchanged.
- Empty Array: If the input array is empty, the pointers will also not move, and the array remains unchanged.