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"]
Constraints:
1 <= s.length <= 105s[i] is a printable ascii character.The #344 Reverse String problem asks you to reverse a string in-place. Since strings are often represented as an array of characters in this problem, the most efficient technique is the two pointers approach. This method avoids creating additional data structures and focuses on swapping characters directly inside the array.
Start by placing one pointer at the beginning of the character array and another at the end. At each step, swap the characters at these two positions and move the pointers toward the center. Continue this process until the pointers meet or cross. This approach ensures every character is moved to its correct reversed position.
The main advantage of this technique is its efficiency. Each character is processed once, resulting in linear time complexity. Because the reversal is done directly within the input array, the algorithm uses constant extra space. This pattern is commonly used in string manipulation problems and is a fundamental application of the two pointers technique.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers (In-place Swap) | O(n) | O(1) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
The entire logic for reversing a string is based on using the opposite directional two-pointer approach!
The two-pointer technique involves using two pointers, one starting at the beginning of the array and the other at the end. Swap the characters at the two pointers and then move the pointers inwards towards each other until they meet or cross. This method efficiently reverses the array in-place with O(1) extra space.
Time Complexity: O(n) where n is the number of characters in the string.
Space Complexity: O(1) as it uses a fixed amount of extra space.
1def reverseString(s):
2 left, right = 0, len(s) - 1
3 while left < right:
4 s[left],
Python's in-place tuple swapping makes the implementation concise and efficient, iterating from both ends until pointers cross.
This approach uses recursion to swap characters at symmetric positions while visually simplifying the problem. The base case is when the left index is not less than the right index.
Time Complexity: O(n).
Space Complexity: O(n) due to call stack depth.
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Reverse String is a very common beginner-level interview question. While simple, it tests understanding of two-pointer techniques, in-place operations, and basic string manipulation.
The optimal approach uses the two pointers technique. One pointer starts at the beginning of the character array and the other at the end, and characters are swapped while moving inward. This ensures the string is reversed in linear time without extra memory.
The problem is typically solved using an array of characters because it allows direct index access and in-place swapping. Arrays make it easy to apply the two-pointer technique efficiently.
The two pointers technique allows you to process elements from both ends of the string simultaneously. By swapping characters and moving inward, you reverse the string efficiently while maintaining constant extra space.
Recursive function in C swaps characters starting from outermost towards the middle, reducing the problem size in each call.