Reverse String

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

Input: s = "hello"
Output: "olleh"
Explanation: Characters are swapped moving inwards from both ends.

Example 2

Input: s = "kodeknight"
Output: "thginkedok"
Explanation: Standard two-pointer swapping until the middle.

Similar Problems

[Reverse String 2](reverse-string-2)

Solution

Below are multiple methods, ordered from the most standard (two pointers) to less typical (XOR swap, library helpers). All demonstrate the same logical reversal with different trade-offs.

Method 1 - Two Pointers (Canonical In-Place)

Intuition

Use one pointer at the left end and one at the right end; swap and converge. This minimizes space and is the standard interview solution.

Approach

Initialize l=0, r=n-1. While l < r, swap characters, increment l, decrement r.

Code

C

void reverseString(char *s) {
    int l = 0, r = (int)strlen(s) - 1;
    while (l < r) {
        char tmp = s[l];
        s[l] = s[r];
        s[r] = tmp;
        ++l; --r;
    }
}

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--;
        }
    }
}

Python

class Solution:
    def reverseString(self, s: list[str]) -> None:
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1

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;
	}
}

Complexity

• ⏰ Time complexity: O(n) – each index swapped at most once.
• 🧺 Space complexity: O(1) – in-place swaps only.

Method 2 - Symmetric Index Swap (Half Loop)

Intuition

Equivalent to Method 1 but frames the loop over the first half only; directly swaps i with n-i-1.

Approach

For i in [0 .. n/2), swap s[i] and s[n-1-i].

Code

Java

class Solution {
  public void reverseString(char[] s) {
    int n = s.length;
    for (int i = 0; i < n / 2; i++) {
      char tmp = s[i];
      s[i] = s[n - 1 - i];
      s[n - 1 - i] = tmp;
    }
  }
}

Rust

pub fn reverse_string(s: &mut [char]) {
    let n = s.len();
    for i in 0..n/2 { s.swap(i, n - 1 - i); }
}

Complexity

• ⏰ Time complexity: O(n) – half the iterations, but still linear.
• 🧺 Space complexity: O(1) – constant extra space.

Method 3 - Recursion

Intuition

Recurse inward: swap the outer pair then recurse on the substring interior. Pedagogical but less efficient due to call overhead.

Approach

Define helper recur(s, l, r): if l >= r stop; swap s[l], s[r]; call recur(l+1, r-1).

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]);
}

Complexity

• ⏰ Time complexity: O(n) – each position processed once.
• 🧺 Space complexity: O(n) – recursion stack depth ≈ n/2 → O(n) call frames.

Method 4 - Stack (Uses Extra Space)

Intuition

Push all characters, then pop to rebuild reversed order. Demonstrates LIFO data structure but wastes memory.

Approach

Traverse string pushing chars; pop sequentially and overwrite original array.

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()

Complexity

• ⏰ Time complexity: O(n) – one pass push + one pass pop.
• 🧺 Space complexity: O(n) – stack stores all characters.

Method 5 - In-Place XOR Swap (Not Recommended)

Intuition

Swaps two characters without a temporary variable using XOR: a ^= b; b ^= a; a ^= b;. Conceptually clever but modern compilers optimize a normal temp swap equally (or better). Less readable and can be error-prone if indices alias.

Approach

Same two-pointer convergence as Method 1, but uses XOR sequence instead of a temporary variable for each swap.

Code

C

#include <string.h>
void reverseStringXor(char *s) {
    int l = 0, r = (int)strlen(s) - 1;
    while (l < r) {
        if (s[l] != s[r]) { // guard: XOR swap breaks if same address (not here) but ok to skip needless ops
            s[l] ^= s[r];
            s[r] ^= s[l];
            s[l] ^= s[r];
        }
        ++l; --r;
    }
}

Trade-offs

Readable temp-swap (Method 1) is preferred in production; XOR adds zero practical benefit and can inhibit some optimizations / confuse reviewers.

Complexity

• ⏰ Time complexity: O(n) – identical iteration pattern to Method 1.
• 🧺 Space complexity: O(1) – in-place.

Method 6 - Language Built-ins / Convenience

Intuition

Leverage library provisions: builder reversal or slicing constructs that internally perform efficient reversal (often similar to Method 1 under the hood).

Approach

Use high-level APIs to emphasize intent over mechanics.

Code

Java (StringBuilder / StringBuffer)

String s = "Game Plan";
String reversed = new StringBuilder(s).reverse().toString();

Python (Slicing)

def reverse_builtin(s: str) -> str:
    return s[::-1]

Complexity

• ⏰ Time complexity: O(n) – must copy / iterate through all characters.
• 🧺 Space complexity: O(n) – new reversed buffer created.

Method Comparison

Method	Time	Space	Notes
1 Two Pointers	O(n)	O(1)	Canonical, optimal
2 Symmetric Half Loop	O(n)	O(1)	Equivalent to Method 1 style variant
3 Recursion	O(n)	O(n)	Educational; stack overhead
4 Stack	O(n)	O(n)	Demonstrates stack; inefficient
5 XOR Swap	O(n)	O(1)	No real benefit; readability cost
6 Built-ins	O(n)	O(n)	Most concise; allocates new buffer

Notes

Preferred practical answer: Method 1 (or Method 2 variant). Include XOR only to illustrate bitwise swap patterns (see also [Swap two number in place without temporary variables](swap-two-number-in-place-without-temporary-variables)). Recursion and stack approaches are mainly pedagogical.