Problem

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

Examples

Example 1:

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

Solution

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
public void reverse(char[] s) {
	int start = 0;
	int end = s.length - 1;
	while (start < end) {
		char tmp = s[start];
		s[start] = arr[end];
		s[end] = tmp;
		++start;
		--end;
	}
}
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

void reverse(char[] s) {
	return reverse(s, 0, s.length());
}

// ------ helper ------

void reverse(char[] x, int beg, int end) {
	char c;

	if (beg >= end) {
		return;
	}

	char temp = x[beg];
	x[beg] = x[end];
	x[end] = temp;

	reverse(x, ++begin, --end);
}

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

public void reverse(char[] arr) {
	Stack<Character> stack = new Stack<>();
	int end = arr.length - 1;
	for (char c: arr) {
		stack.push(c);
	}
	int i = 0;
	while(!stack.isEmpty()) {
		arr[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