Reverse String

Reverse a string in-place using O(1) extra memory.

Language Selection

Choose your preferred programming language

Showing: Python

Reverse String

Problem Statement

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.

Examples

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Explanation: The string "hello" is reversed to "olleh".

Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
Explanation: The string "Hannah" is reversed to "hannaH".

Constraints

1 <= s.length <= 10^5
s[i] is a printable ascii character.

Approach 1: Two Pointers (Optimal)

Algorithm

Use two pointers starting from both ends and swap characters until they meet.

Steps:

Initialize left pointer to 0 and right pointer to length-1
While left < right:
- Swap characters at left and right positions
- Move left pointer right and right pointer left
The string is now reversed in-place

Implementation

Python:

def reverseString(s):
    """
    Reverse string in-place using two pointers
    Time: O(n)
    Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

Java:

class Solution {
    /**
     * Reverse string in-place using two pointers
     * Time: O(n)
     * Space: O(1)
     */
    public 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--;
        }
    }
}

Go:

func reverseString(s []byte) {
    /**
     * Reverse string in-place using two pointers
     * Time: O(n)
     * Space: O(1)
     */
    left, right := 0, len(s)-1
    
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

JavaScript:

/**
 * Reverse string in-place using two pointers
 * Time: O(n)
 * Space: O(1)
 */
function reverseString(s) {
    let left = 0;
    let right = s.length - 1;
    
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]];
        left++;
        right--;
    }
}

C#:

public class Solution {
    /// <summary>
    /// Reverse string in-place using two pointers
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public 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--;
        }
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass through half the array
Space Complexity: O(1) - Only using constant extra space

Approach 2: Recursive (Alternative)

Algorithm

Use recursion to reverse the string by swapping characters at the ends.

Steps:

Base case: if left >= right, return
Swap characters at left and right positions
Recursively call with left+1 and right-1

Implementation

Python:

def reverseString_recursive(s):
    """
    Reverse string using recursion
    Time: O(n)
    Space: O(n) - recursion stack
    """
    def helper(left, right):
        if left >= right:
            return
        
        s[left], s[right] = s[right], s[left]
        helper(left + 1, right - 1)
    
    helper(0, len(s) - 1)

Java:

class Solution {
    /**
     * Reverse string using recursion
     * Time: O(n)
     * Space: O(n) - recursion stack
     */
    public void reverseStringRecursive(char[] s) {
        helper(s, 0, s.length - 1);
    }
    
    private void helper(char[] s, int left, int right) {
        if (left >= right) {
            return;
        }
        
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        
        helper(s, left + 1, right - 1);
    }
}

Go:

func reverseStringRecursive(s []byte) {
    /**
     * Reverse string using recursion
     * Time: O(n)
     * Space: O(n) - recursion stack
     */
    helper(s, 0, len(s)-1)
}

func helper(s []byte, left, right int) {
    if left >= right {
        return
    }
    
    s[left], s[right] = s[right], s[left]
    helper(s, left+1, right-1)
}

JavaScript:

/**
 * Reverse string using recursion
 * Time: O(n)
 * Space: O(n) - recursion stack
 */
function reverseStringRecursive(s) {
    function helper(left, right) {
        if (left >= right) {
            return;
        }
        
        [s[left], s[right]] = [s[right], s[left]];
        helper(left + 1, right - 1);
    }
    
    helper(0, s.length - 1);
}

C#:

public class Solution {
    /// <summary>
    /// Reverse string using recursion
    /// Time: O(n)
    /// Space: O(n) - recursion stack
    /// </summary>
    public void ReverseStringRecursive(char[] s) {
        Helper(s, 0, s.Length - 1);
    }
    
    private void Helper(char[] s, int left, int right) {
        if (left >= right) {
            return;
        }
        
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        
        Helper(s, left + 1, right - 1);
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass through half the array
Space Complexity: O(n) - Recursion stack depth

Approach 3: Built-in Functions (Alternative)

Algorithm

Use built-in string reversal functions available in some languages.

Steps:

Convert array to string
Use built-in reverse function
Convert back to array

Implementation

Python:

def reverseString_builtin(s):
    """
    Reverse string using built-in functions
    Time: O(n)
    Space: O(n) - temporary string
    """
    s[:] = s[::-1]  # Slice assignment modifies original array

Java:

class Solution {
    /**
     * Reverse string using built-in functions
     * Time: O(n)
     * Space: O(n) - temporary string
     */
    public void reverseStringBuiltin(char[] s) {
        String str = new String(s);
        String reversed = new StringBuilder(str).reverse().toString();
        
        for (int i = 0; i < s.length; i++) {
            s[i] = reversed.charAt(i);
        }
    }
}

Go:

func reverseStringBuiltin(s []byte) {
    /**
     * Reverse string using built-in functions
     * Time: O(n)
     * Space: O(n) - temporary string
     */
    str := string(s)
    reversed := ""
    for i := len(str) - 1; i >= 0; i-- {
        reversed += string(str[i])
    }
    copy(s, []byte(reversed))
}

JavaScript:

/**
 * Reverse string using built-in functions
 * Time: O(n)
 * Space: O(n) - temporary string
 */
function reverseStringBuiltin(s) {
    const reversed = s.slice().reverse();
    s.splice(0, s.length, ...reversed);
}

C#:

public class Solution {
    /// <summary>
    /// Reverse string using built-in functions
    /// Time: O(n)
    /// Space: O(n) - temporary string
    /// </summary>
    public void ReverseStringBuiltin(char[] s) {
        string str = new string(s);
        char[] reversed = str.Reverse().ToArray();
        
        for (int i = 0; i < s.Length; i++) {
            s[i] = reversed[i];
        }
    }
}

Complexity Analysis

Time Complexity: O(n) - Depends on implementation
Space Complexity: O(n) - Temporary string storage

Key Insights

Two Pointers: Most efficient approach with O(1) space
In-Place Modification: Must modify the original array
Swap Operation: Exchange characters at opposite ends
Recursion Trade-off: Simpler logic but uses O(n) space
Built-in Functions: Convenient but may use extra space

Edge Cases

Empty String: Handle empty array gracefully
Single Character: Single character string is already reversed
Two Characters: Simple swap operation
Odd Length: Middle character stays in place
Even Length: All characters are swapped

Test Cases

def test_reverseString():
    # Test case 1
    s1 = ["h","e","l","l","o"]
    reverseString(s1)
    assert s1 == ["o","l","l","e","h"]
    
    # Test case 2
    s2 = ["H","a","n","n","a","h"]
    reverseString(s2)
    assert s2 == ["h","a","n","n","a","H"]
    
    # Edge cases
    s3 = ["a"]
    reverseString(s3)
    assert s3 == ["a"]
    
    s4 = ["a", "b"]
    reverseString(s4)
    assert s4 == ["b", "a"]
    
    s5 = []
    reverseString(s5)
    assert s5 == []
    
    print("All tests passed!")

test_reverseString()

Follow-up Questions

Reverse Words: Reverse the order of words in a sentence?
Reverse Vowels: Reverse only the vowels in a string?
Reverse K Groups: Reverse every k characters?
Reverse Linked List: Reverse a linked list?
Palindrome Check: Check if a string is a palindrome?

Common Mistakes

Not Modifying In-Place: Creating a new array instead of modifying original
Wrong Loop Condition: Using <= instead of < in loop condition
Index Out of Bounds: Not handling empty or single character arrays
Space Complexity: Using O(n) space when O(1) is required
Swap Logic: Incorrect swap implementation

Interview Tips

Start with Two Pointers: Most efficient and intuitive approach
Explain In-Place: Emphasize the O(1) space requirement
Handle Edge Cases: Mention empty and single character cases
Discuss Alternatives: Show knowledge of different approaches
Follow-up Ready: Be prepared for related problems

Concept Explanations

Two Pointers Technique: This is a fundamental technique where we use two pointers starting from opposite ends of the array and move them towards each other. It’s particularly useful for problems involving array manipulation, searching, or validation.

In-Place Algorithm: An in-place algorithm modifies the input data structure without using additional memory proportional to the input size. This is important for memory-constrained environments and is often a requirement in coding interviews.

Swap Operation: The core operation in string reversal is swapping characters at symmetric positions. This can be done using temporary variables or language-specific features like tuple unpacking in Python.

Why Two Pointers Work: By starting from both ends and moving towards the center, we ensure that each character is swapped exactly once. The algorithm terminates when the pointers meet (or cross), ensuring we don’t over-process any characters.

Space-Time Trade-off: The iterative two-pointers approach gives us O(1) space complexity, while the recursive approach uses O(n) space due to the call stack but might be more intuitive to understand.