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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

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]

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)

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

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

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

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.