Reverse String solution and explanation
TCS
Google
Infosys
9 more videos on this problem
Reverse String - 3 Ways - Leetcode 344 - PythonNeetCode · 9:03 · 89K views
Leetcode 344. Reverse StringFraz · 10:05 · 38K views
Reverse String - Leetcode 344 - 2 Pointers - (Python)Greg Hogg · 4:37 · 14K views
Leetcode | 344. Reverse String | Easy | Java SolutionDeveloper Docs · 3:55 · 4K views
Reverse String | LeetCode 344 | Coding Interview TutorialTerrible Whiteboard · 6:14 · 4K views
LeetCode 344: Reverse String - Interview Prep Ep 56Fisher Coder · 5:21 · 1K views
Reverse String - LeetCode 344 - Coding Interview QuestionsOne Code Man · 3:51 · 1K views
Can You Reverse a String? (LeetCode 344: Reverse String)Code With Zi · 3:01 · 1K views
344 Reverse String LeetСode (Google Interview Question) JavaScriptdev alex · 4:04 · 989 views
Reverse String | LeetCode 344 | JavaTech Tutor · 4:10 · 260 views
The problem
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.
Approach overview
Problem Overview: You are given a character array s and must reverse it in-place. The function cannot allocate extra space for another array; the reversal must happen by modifying the original array directly.
Approach 1: Two-Pointer Approach (O(n) time, O(1) space)
This is the standard in-place solution. Use two indices: one starting at the beginning of the array (left) and one at the end (right). Swap the characters at these positions, then move left++ and right-- until the pointers meet in the middle. Each element is visited at most once, giving O(n) time complexity. Since the swaps happen directly inside the input array without extra storage, the space complexity remains O(1). This technique is a classic application of the Two Pointers pattern and works efficiently for problems where you process elements from both ends of a sequence.
The key insight is that reversing a sequence simply means exchanging symmetric elements around the center. For example, the first character swaps with the last, the second with the second-last, and so on. You only need to process half the array because each swap places two characters in their final position. This approach is optimal for array-based string manipulation problems where in-place updates are required.
Approach 2: Recursive Approach (O(n) time, O(n) space)
The recursive solution performs the same symmetric swaps but delegates the remaining work to recursive calls. Start with two indices (left and right). Swap s[left] and s[right], then recursively call the function with left + 1 and right - 1. The recursion stops when left >= right, meaning the middle of the array has been reached.
Each recursive call processes one pair of characters, so the total number of operations is still O(n). However, the recursion stack stores up to n/2 function calls, resulting in O(n) auxiliary space. While this approach is conceptually elegant and demonstrates understanding of recursion, it is less space-efficient than the iterative two-pointer method.
Recommended for interviews: The two-pointer approach is what interviewers expect. It demonstrates awareness of in-place array manipulation and optimal space usage. Mentioning the recursive version shows deeper algorithmic understanding, but the iterative two-pointer solution is the cleanest and most efficient implementation.
Approach 1: 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.
def reverseString(s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
s = ['h', 'e', 'l', 'l', 'o']
reverseString(s)
print(s)class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}#include <vector>
using namespace std;
void reverseString(vector<char>& s) {
int left = 0, right = s.size() - 1;
while (left < right) {
swap(s[left++], s[right--]);
}
}function reverseString(s) {
let left = 0, right = s.length - 1;
while (left < right) {
[s[left], s[right]] = [s[right], s[left]];
left++;
right--;
}
}
const s = ['h', 'e', 'l', 'l', 'o'];
reverseString(s);
console.log(s);#include <stdio.h>
void reverseString(char* s, int sSize) {
int left = 0, right = sSize - 1;
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}public class Solution {
public void ReverseString(char[] s) {
int left = 0, right = s.Length - 1;
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}Python's in-place tuple swapping makes the implementation concise and efficient, iterating from both ends until pointers cross.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Recursive Approach
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.
def reverseUtil(s, left, right):
if left >= right:
return
s[left], s[right] = s[right], s[left]
reverseUtil(s, left + 1, right - 1)
def reverseString(s):
reverseUtil(s, 0, len(s) - 1)
s = ['h', 'e', 'l', 'l', 'o']
reverseString(s)
print(s)class Solution {
private void reverseUtil(char[] s, int left, int right) {
if (left >= right) return;
char temp = s[left];
s[left] = s[right];
s[right] = temp;
reverseUtil(s, left + 1, right - 1);
}
public void reverseString(char[] s) {
reverseUtil(s, 0, s.length - 1);
}
}#include <vector>
using namespace std;
void reverseUtil(vector<char>& s, int left, int right) {
if (left >= right) return;
swap(s[left], s[right]);
reverseUtil(s, left + 1, right - 1);
}
void reverseString(vector<char>& s) {
reverseUtil(s, 0, s.size() - 1);
}function reverseUtil(s, left, right) {
if (left >= right) return;
[s[left], s[right]] = [s[right], s[left]];
reverseUtil(s, left + 1, right - 1);
}
function reverseString(s) {
reverseUtil(s, 0, s.length - 1);
}
const s = ['h', 'e', 'l', 'l', 'o'];
reverseString(s);
console.log(s);#include <stdio.h>
void reverseUtil(char* s, int left, int right) {
if (left >= right) return;
char temp = s[left];
s[left] = s[right];
s[right] = temp;
reverseUtil(s, left + 1, right - 1);
}
void reverseString(char* s, int sSize) {
reverseUtil(s, 0, sSize - 1);
}public class Solution {
private void ReverseUtil(char[] s, int left, int right) {
if (left >= right) return;
char temp = s[left];
s[left] = s[right];
s[right] = temp;
ReverseUtil(s, left + 1, right - 1);
}
public void ReverseString(char[] s) {
ReverseUtil(s, 0, s.Length - 1);
}
}Python's recursion easily reverses the string by employing a helper function that divides the problem and swaps characters.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 3: Two Pointers
We use two pointers i and j, initially pointing to the start and end of the array respectively. Each time, we swap the elements at i and j, then move i forward and j backward, until i and j meet.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
/**
Do not return anything, modify s in-place instead.
*/
function reverseString(s: string[]): void {
for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
[s[i], s[j]] = [s[j], s[i]];
}
}func reverseString(s []byte) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}impl Solution {
pub fn reverse_string(s: &mut Vec<char>) {
let mut i = 0;
let mut j = s.len() - 1;
while i < j {
s.swap(i, j);
i += 1;
j -= 1;
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n). |
| Recursive Approach | Time Complexity: O(n). |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Approach | O(n) | O(1) | Best general solution when the string/array must be reversed in-place with minimal memory. |
| Recursive Approach | O(n) | O(n) | Useful for demonstrating recursion concepts or practicing divide-and-conquer thinking. |
Frequently asked questions
Is Reverse String easy or hard?
Reverse String is classified as an easy problem. The logic is straightforward once you recognize the symmetric swap pattern, making it a common warm-up problem for practicing arrays, strings, and the two-pointer technique.
How to solve Reverse String in O(n)?
Use two pointers that start at opposite ends of the character array. Swap the characters at the pointers, then move them inward until they meet. This performs the reversal in linear time O(n) and constant space O(1) without allocating a new string.
Reverse String Python or Java solution?
In Python, swap characters using two indices inside a loop while left < right. In Java, use a char array and perform in-place swaps with a temporary variable. Both implementations follow the same two-pointer logic and run in O(n) time with O(1) extra space.
What is the best approach for Reverse String?
The two-pointer approach is the most efficient method. Start with one pointer at the beginning and another at the end of the array, swap the characters, and move both pointers toward the center. This completes the reversal in O(n) time and O(1) space since the operation is done in-place.
What data structure is used in Reverse String?
The problem operates directly on a character array, which behaves like a mutable string structure. The algorithm relies on index-based access and swaps, combined with the two-pointer technique for efficient traversal from both ends.
What is the time complexity of Reverse String?
The optimal solution runs in O(n) time because each character is processed at most once. In the two-pointer approach, roughly n/2 swaps occur. Recursive implementations also take O(n) time but use additional stack space.
Is Reverse String asked at Google, Amazon, or Meta?
Reverse String is a common introductory string manipulation problem that appears in coding interviews and screening rounds at companies like Amazon and Meta. It is often used to test understanding of in-place array operations and the two-pointer technique.