Reverse a String
Problem
Given a string S, reverse the string and return the reversed result.
Reversing a string means the first character becomes the last, the second becomes the second last, and so on.
This is one of the most fundamental problems in Data Structures and Algorithms, often used to understand string manipulation, two-pointer techniques, and recursion.
Example
Input
S = "hello"
Output
olleh
Explanation
The characters of the string are reversed:
h e l l o
↓ ↓ ↓ ↓ ↓
o l l e h
Approach 1: Two Pointer / Iterative Swap
Idea
This approach uses the two-pointer technique.
Steps:
- Convert the string into a character array (if needed).
- Initialize two pointers:
- left = 0
- right = length - 1
- Swap characters at left and right.
- Move pointers:
- left++
- right--
- Continue until left < right.
Time Complexity
O(n)
Space Complexity
O(1)
Implementation
C
#include
#include
void reverseString(char str[]) {
int left = 0;
int right = strlen(str) - 1;
while (left < right) {
char temp = str[left];
str[left] = str[right];
str[right] = temp;
left++;
right--;
}
}
int main() {
char str[] = "hello";
reverseString(str);
printf("Reversed String: %s\n", str);
return 0;
}
Output
Reversed String: olleh
C++
#include
#include
using namespace std;
void reverseString(string &s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
}
int main() {
string s = "hello";
reverseString(s);
cout << "Reversed String: " << s << endl;
return 0;
}
Output
Reversed String: olleh
Java
public class ReverseString {
public static void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
public static void main(String[] args) {
String str = "hello";
char[] arr = str.toCharArray();
reverseString(arr);
System.out.println("Reversed String: " + new String(arr));
}
}
Output
Reversed String: olleh
Python
def reverse_string(s):
arr = list(s)
left = 0
right = len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return ''.join(arr)
s = "hello"
result = reverse_string(s)
print("Reversed String:", result)
Output
Reversed String: olleh
JavaScript
function reverseString(str) {
let arr = str.split("");
let left = 0;
let right = arr.length - 1;
while (left < right) {
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
return arr.join("");
}
let s = "hello";
console.log("Reversed String:", reverseString(s));
Output
Reversed String: olleh
Approach 2: Recursion
Idea
Recursion reverses the string by solving smaller subproblems.
Steps:
- Base case: If the string length is 0 or 1, return the string.
- Recursive case:
- Reverse the substring from index 1 to end.
- Append the first character at the end.
Example:
reverse("hello")
= reverse("ello") + 'h'
= reverse("llo") + 'e' + 'h'
= reverse("lo") + 'l' + 'e' + 'h'
= reverse("o") + 'l' + 'l' + 'e' + 'h'
Time Complexity
O(n)
Space Complexity
O(n) (recursion stack)
Implementation
C
#include
#include
void reverse(char str[], int start, int end) {
if (start >= end)
return;
char temp = str[start];
str[start] = str[end];
str[end] = temp;
reverse(str, start + 1, end - 1);
}
int main() {
char str[] = "hello";
reverse(str, 0, strlen(str) - 1);
printf("Reversed String: %s\n", str);
return 0;
}
Output
Reversed String: olleh
C++
#include
using namespace std;
void reverseString(string &s, int left, int right) {
if (left >= right)
return;
swap(s[left], s[right]);
reverseString(s, left + 1, right - 1);
}
int main() {
string s = "hello";
reverseString(s, 0, s.length() - 1);
cout << "Reversed String: " << s << endl;
return 0;
}
Output
Reversed String: olleh
Java
public class ReverseStringRec {
static void reverse(char[] s, int left, int right) {
if (left >= right)
return;
char temp = s[left];
s[left] = s[right];
s[right] = temp;
reverse(s, left + 1, right - 1);
}
public static void main(String[] args) {
String str = "hello";
char[] arr = str.toCharArray();
reverse(arr, 0, arr.length - 1);
System.out.println("Reversed String: " + new String(arr));
}
}
Output
Reversed String: olleh
Python
def reverse_string(arr, left, right):
if left >= right:
return
arr[left], arr[right] = arr[right], arr[left]
reverse_string(arr, left + 1, right - 1)
s = "hello"
arr = list(s)
reverse_string(arr, 0, len(arr) - 1)
print("Reversed String:", ''.join(arr))
Output
Reversed String: olleh
JavaScript
function reverseString(arr, left, right) {
if (left >= right)
return;
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
reverseString(arr, left + 1, right - 1);
}
let s = "hello";
let arr = s.split("");
reverseString(arr, 0, arr.length - 1);
console.log("Reversed String:", arr.join(""));
Output
Reversed String: olleh