344. Reverse String - Explanation

Description

You are given an array of characters which represents a string s. Write a function which reverses a string.

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

Example 1:

Input: s = ["n","e","e","t"]

Output: ["t","e","e","n"]

Example 2:

Input: s = ["r","a","c","e","c","a","r"]

Output: ["r","a","c","e","c","a","r"]

Constraints:

1 <= s.length < 100,000
s[i] is a printable ascii character.

Topics

Two Pointers String

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Basic array indexing and iteration
Two Pointers - Using pointers at opposite ends to traverse and modify data
In-place Modification - Modifying data structures without using extra space

1. Array

Intuition

The simplest approach is to build the reversed string in a separate array. We iterate through the original array from the end to the beginning, collecting characters in a new temporary array. Then we copy the reversed characters back to the original array. This works because reading backward gives us characters in reverse order.

Algorithm

Create a temporary array tmp to store characters.
Iterate through the input array from the last index to the first using index i.
Append each character to tmp.
Copy all characters from tmp back to the original array s.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        tmp = []
        for i in range(len(s) - 1, -1, -1):
            tmp.append(s[i])
        for i in range(len(s)):
            s[i] = tmp[i]

class Solution {
public:
    void reverseString(vector<char>& s) {
        vector<char> tmp;
        for (int i = s.size() - 1; i >= 0; i--) {
            tmp.push_back(s[i]);
        }
        for (int i = 0; i < s.size(); i++) {
            s[i] = tmp[i];
        }
    }
};

class Solution {
    /**
     * @param {character[]} s
     * @return {void} Do not return anything, modify s in-place instead.
     */
    reverseString(s) {
        const tmp = [];
        for (let i = s.length - 1; i >= 0; i--) {
            tmp.push(s[i]);
        }
        for (let i = 0; i < s.length; i++) {
            s[i] = tmp[i];
        }
    }
}

public class Solution {
    public void ReverseString(char[] s) {
        char[] tmp = new char[s.Length];
        int n = s.Length;

        for (int i = 0; i < n; i++) {
            tmp[i] = s[n - 1 - i];
        }

        for (int i = 0; i < n; i++) {
            s[i] = tmp[i];
        }
    }
}

class Solution {
    fun reverseString(s: CharArray): Unit {
        val tmp = CharArray(s.size)
        val n = s.size

        for (i in 0 until n) {
            tmp[i] = s[n - 1 - i]
        }

        for (i in 0 until n) {
            s[i] = tmp[i]
        }
    }
}

class Solution {
    func reverseString(_ s: inout [Character]) {
        var tmp = [Character]()
        for i in stride(from: s.count - 1, through: 0, by: -1) {
            tmp.append(s[i])
        }
        for i in 0..<s.count {
            s[i] = tmp[i]
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Recursion

Intuition

We can reverse a string recursively by thinking of it as swapping the outermost characters, then reversing the inner substring. If we have pointers at both ends (l and r), we first recurse to handle the inner portion, then swap the current pair on the way back up. This naturally reverses the array through the call stack.

Algorithm

Define a recursive helper function reverse(l, r) where l is the left index and r is the right index.
Base case: if l >= r, return (nothing to swap).
Recurse on the inner portion: call reverse(l + 1, r - 1).
After returning, swap s[l] and s[r].
Start the recursion with reverse(0, len(s) - 1).

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        def reverse(l, r):
            if l < r:
                reverse(l + 1, r - 1)
                s[l], s[r] = s[r], s[l]

        reverse(0, len(s) - 1)

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

    private void reverse(char[] s, int l, int r) {
        if (l < r) {
            reverse(s, l + 1, r - 1);
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
        }
    }
}

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s, 0, s.size() - 1);
    }

private:
    void reverse(vector<char>& s, int l, int r) {
        if (l < r) {
            reverse(s, l + 1, r - 1);
            swap(s[l], s[r]);
        }
    }
};

class Solution {
    /**
     * @param {character[]} s
     * @return {void} Do not return anything, modify s in-place instead.
     */
    reverseString(s) {
        const reverse = (l, r) => {
            if (l < r) {
                reverse(l + 1, r - 1);
                [s[l], s[r]] = [s[r], s[l]];
            }
        };
        reverse(0, s.length - 1);
    }
}

public class Solution {
    public void ReverseString(char[] s) {
        Reverse(s, 0, s.Length - 1);
    }

    private void Reverse(char[] s, int left, int right) {
        if (left < right) {
            Reverse(s, left + 1, right - 1);
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
        }
    }
}

func reverseString(s []byte) {
    var reverse func(l, r int)
    reverse = func(l, r int) {
        if l < r {
            reverse(l+1, r-1)
            s[l], s[r] = s[r], s[l]
        }
    }
    reverse(0, len(s)-1)
}

class Solution {
    fun reverseString(s: CharArray): Unit {
        reverse(s, 0, s.size - 1)
    }

    private fun reverse(s: CharArray, l: Int, r: Int) {
        if (l < r) {
            reverse(s, l + 1, r - 1)
            val temp = s[l]
            s[l] = s[r]
            s[r] = temp
        }
    }
}

class Solution {
    func reverseString(_ s: inout [Character]) {
        reverse(&s, 0, s.count - 1)
    }

    private func reverse(_ s: inout [Character], _ l: Int, _ r: Int) {
        if l < r {
            reverse(&s, l + 1, r - 1)
            let temp = s[l]
            s[l] = s[r]
            s[r] = temp
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Stack

Intuition

A stack follows Last-In-First-Out (LIFO) order, which is perfect for reversing. If we push all characters onto a stack, then pop them off one by one, we get the characters in reverse order. This exploits the stack's natural behavior to achieve the reversal.

Algorithm

Create an empty stack.
Push every character from the input array s onto the stack.
Iterate through the array indices i, popping from the stack and writing each character back to s.
The array is now reversed in place.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        stack = []
        for c in s:
            stack.append(c)
        i = 0
        while stack:
            s[i] = stack.pop()
            i += 1

public class Solution {
    public void reverseString(char[] s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s) {
            stack.push(c);
        }
        int i = 0;
        while (!stack.isEmpty()) {
            s[i++] = stack.pop();
        }
    }
}

class Solution {
public:
    void reverseString(vector<char>& s) {
        stack<char> stk;
        for (char& c : s) {
            stk.push(c);
        }
        int i = 0;
        while (!stk.empty()) {
            s[i++] = stk.top();
            stk.pop();
        }
    }
};

class Solution {
    /**
     * @param {character[]} s
     * @return {void} Do not return anything, modify s in-place instead.
     */
    reverseString(s) {
        const stack = [];
        for (const c of s) {
            stack.push(c);
        }
        let i = 0;
        while (stack.length) {
            s[i++] = stack.pop();
        }
    }
}

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

        foreach (char c in s) {
            stack.Push(c);
        }

        for (int i = 0; i < s.Length; i++) {
            s[i] = stack.Pop();
        }
    }
}

func reverseString(s []byte) {
    stack := make([]byte, 0)
    for _, c := range s {
        stack = append(stack, c)
    }
    for i := 0; i < len(s); i++ {
        s[i] = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
    }
}

class Solution {
    fun reverseString(s: CharArray): Unit {
        val stack = ArrayDeque<Char>()
        for (c in s) {
            stack.addLast(c)
        }
        for (i in s.indices) {
            s[i] = stack.removeLast()
        }
    }
}

class Solution {
    func reverseString(_ s: inout [Character]) {
        var stack = [Character]()
        for c in s {
            stack.append(c)
        }
        for i in 0..<s.count {
            s[i] = stack.removeLast()
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Built-In Function

Intuition

Most programming languages provide a built-in method to reverse arrays or lists. These functions are typically optimized and handle the reversal in place efficiently. While this approach is the simplest to write, it hides the underlying algorithm.

Algorithm

Call the language's built-in reverse function on the input array.
The array is modified in place.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

public class Solution {
    public void reverseString(char[] s) {
        List<Character> list = new ArrayList<>();
        for (char c : s) {
            list.add(c);
        }
        Collections.reverse(list);

        for (int i = 0; i < s.length; i++) {
            s[i] = list.get(i);
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

5. Two Pointers

Intuition

The most efficient approach uses two pointers starting at opposite ends of the array. We swap the characters at these pointers, then move them toward each other. When the pointers meet or cross, every character has been swapped exactly once, and the array is reversed. This achieves O(1) space since we only swap in place.

Algorithm

Initialize two pointers: l at index 0 and r at the last index.
While l < r:
- Swap s[l] and s[r].
- Increment l and decrement r.
The array s is now reversed in place.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1

public class Solution {
    public void reverseString(char[] s) {
        int l = 0, r = s.length - 1;
        while (l < r) {
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

class Solution {
    /**
     * @param {character[]} s
     * @return {void} Do not return anything, modify s in-place instead.
     */
    reverseString(s) {
        let l = 0,
            r = s.length - 1;
        while (l < r) {
            [s[l], s[r]] = [s[r], s[l]];
            l++;
            r--;
        }
    }
}

public class Solution {
    public void ReverseString(char[] s) {
        int l = 0, r = s.Length - 1;
        while (l < r) {
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

class Solution {
    fun reverseString(s: CharArray): Unit {
        var l = 0
        var r = s.size - 1
        while (l < r) {
            val temp = s[l]
            s[l] = s[r]
            s[r] = temp
            l++
            r--
        }
    }
}

class Solution {
    func reverseString(_ s: inout [Character]) {
        var l = 0
        var r = s.count - 1
        while l < r {
            let temp = s[l]
            s[l] = s[r]
            s[r] = temp
            l += 1
            r -= 1
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Using Incorrect Loop Termination Condition

When using two pointers, the loop should terminate when l >= r, not when l > r. Using l != r works for odd-length strings but is less intuitive. The condition l < r correctly handles both even and odd length arrays.

Returning a New String Instead of Modifying In-Place

The problem requires modifying the input array in-place. A common mistake is creating a new reversed array or string and returning it, which violates the in-place requirement and uses unnecessary extra space.