Problem

Write a function that takes a string as input and returns the string reversed.

You must do this by modifying the input array in-place with O(1) extra memory.

Examples

Example 1:

Given s = "hello", return "olleh".
Given s = “kodeknight” , return “thginkedok“.

Similar Problems

Reverse String 2

Solution

Video explanation

Here is the video explaining these method in detail. Please check it out:

Method 0 - Iterative, Not in Place

In Java, string is immutable. So, cannot do in place!.

public String reverseString(String s) {
	int n = s.length;
	char[] reversed = s.toCharArray();
	return reverse(reversed);
}

Method 1 - Iterative in-place using Two Pointers

Code

C
void reverseString(char* str)
{
    int i, j;
    char temp;
    i=j=temp=0;

    j=strlen(str)-1;
    for (i=0; i<j; i++, j--)
    {
        temp=str[i];
        str[i]=str[j];
        str[j]=temp;
    }
}
Java
class Solution {
    public void reverseString(char[] s) {
        // Initialize two pointers
        int left = 0;
        int right = s.length - 1;
        
        // Continue swapping while left pointer is less than or equal to right pointer
        while (left < right) {
            // Swap the characters at left and right positions
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            
            // Move towards the center
            left++;
            right--;
        }
    }
}
Rust
pub fn reverse_string(s: &mut Vec<char>) {
	let mut left_index = 0;
	let mut right_index = s.len() - 1;
	while left_index < right_index {
		let temp = s[left_index];
		s[left_index] = s[right_index];
		s[right_index] = temp;
		left_index += 1;
		right_index -= 1;
	}
}

Method 2 - Iterative, loop till n/2 kind of like Two Pointers

Code

Java
public void reverse(char[] s) {
	int n = s.length - 1;

	int n = s.length() - 1;
	for (int i = 0; i < n / 2; i++){
		char c = reversed[i];
		reversed[i] = reversed[n-i-1];
		reversed[n-i-1] = c;
	}
	return String.valueOf(reversed);
}
Rust
pub fn reverse_string(s: &mut Vec<char>) {
	let mut i = 0;
	let n = s.len();

	while i < n / 2 {
		s.swap(i, n - i - 1);
		i += 1;
	}
}

Method 3 - Using Recursion

Code

Java
public class Solution {
    public void reverseString(char[] s) {
        helper(s, 0, s.length - 1);
    }

    private void reverseHelper(char[] s, int left, int right) {
        if (left >= right) {
            return;
        }

        // Swap the characters at left and right
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;

        // Recursive call to reverse the inner substring
        helper(s, left + 1, right - 1);
    }
}
Python
class Solution:
    def reverse_string(self, s: list) -> None:
        self.helper(s, 0, len(s) - 1)
    
    def _reverse_helper(self, s: list, left: int, right: int) -> None:
        if left >= right:
            return
        
        # Swap the characters at left and right
        s[left], s[right] = s[right], s[left]
        
        # Recursive call to reverse the inner substring
        self.helper(s, left + 1, right - 1)
Rust
pub fn reverse_string(s: &mut Vec<char>) {
	Self::reverse(&mut s[..]);
}

fn reverse(s: &mut [char]) {
	let len = s.len();
	if len < 2 {
		return;
	}

	s.swap(0, len - 1);

	Self::reverse(&mut s[1..len - 1]);
}

Time complexity - O(n) in both cases. Preferred solution here is iterative one. In recursion method we swap characters at the begin and at the end and then move towards the middle of the string. This method is inefficient due to repeated function calls and extra space used due to recursion.

Method 4 - Iterative Using Stack

Code

Java
public class Solution {
    public void reverseString(char[] s) {
        Stack<Character> stack = new Stack<Character>();

        // Push all characters of the string onto the stack
        for (char c : s) {
            stack.push(c);
        }

        // Pop all characters from the stack and put them back into the string
        for (int i = 0; i < s.length; i++) {
            s[i] = stack.pop();
        }
    }
}
Python
class Solution:
    def reverse_string(self, s: list) -> None:
        stack = []

        # Push all characters of the string onto the stack
        for char in s:
            stack.append(char)

        # Pop all characters from the stack and put them back into the string
        for i in range(len(s)):
            s[i] = stack.pop()

Time Complexity : O(n) where n is the length of the given input string Space Complexity: O(n) as we are using stack data structure.

Method 5 - Using xor to swap (selective programming language)

Reverse a string in C using as little additional memory as possible

Some Shortcuts

Java

Using Java StringBuffer Reverse

StringBuffer buffer = new StringBuffer("Game Plan");
buffer.reverse();
System.out.println(buffer); // Prints: nalP emaG

Using String Builder Reverse

StringBuffer sb = new StringBuffer("Game Plan");
sb.reverse();
System.out.println(sb); // Prints: nalP emaG

Python

greeting = 'Hello, World!'
print(greeting[::-1]) # !dlroW ,olleH