Reverse String

LeetCode 344: Reverse String Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a two-pointer approach to swap characters from the outer edges inward until the pointers meet in the center.

The LeetCode 344 problem asks us to reverse a string provided as an array of characters. The critical constraint is that the modification must be performed in-place, meaning we cannot allocate a new array or string to hold the result. We must achieve this with $O(1)$ extra memory. This is a fundamental algorithmic task often used to test understanding of memory management and array manipulation.

Brute Force Approach for Reverse String

The naive or brute force approach typically involves creating a secondary data structure to hold the reversed characters.

1. Initialize a new empty array of the same length as the input s.
2. Iterate through the input array s from the last index down to the first.
3. Append each character to the new array.
4. Copy the new array back into s (or return it, depending on the specific API).

Pseudo-code:

function reverseString(s):
    newArray = []
    for i from length(s) - 1 down to 0:
        newArray.append(s[i])
    s = newArray

Complexity Analysis:

• Time Complexity: $O(N)$, where $N$ is the number of characters. We iterate through the array once.
• Space Complexity: $O(N)$. We allocate a new array of size $N$.

Why it fails: While this approach produces the correct output, it violates the problem's strict constraint of $O(1)$ extra memory. In an interview context, allocating linear space when constant space is requested is considered a failure to meet requirements.

Algorithm Strategy: Two Pointer Patterns

The strategy relies on maintaining two indices, left and right, which define the boundaries of the characters currently being swapped.

1. Initialization: Set the left pointer to the beginning of the array (0) and the right pointer to the end of the array (s.length - 1).
2. Iteration Condition: Continue the process as long as left is strictly less than right. If they are equal, the middle character (in an odd-length string) does not need to move. If left > right, the pointers have crossed, and the work is done.
3. Swap Operation: Inside the loop, perform a standard swap of the values at s[left] and s[right].
4. Pointer Convergence: Increment left by 1 and decrement right by 1 to move inward toward the center of the array.

Execution Flow

1. Start: Input s = ["h", "e", "l", "l", "o"].

   • left = 0 (points to 'h')
   • right = 4 (points to 'o')

2. Iteration 1:

   • Check left < right ($0 < 4$): True.
   • Swap s[0] and s[4]. Array becomes ["o", "e", "l", "l", "h"].
   • Increment left to 1.
   • Decrement right to 3.

3. Iteration 2:

   • Check left < right ($1 < 3$): True.
   • Swap s[1] and s[3]. Array becomes ["o", "l", "l", "e", "h"].
   • Increment left to 2.
   • Decrement right to 2.

4. Iteration 3:

   • Check left < right ($2 < 2$): False.
   • Loop terminates.

5. End: The array is modified in-place to ["o", "l", "l", "e", "h"].

Proof of Correctness

The algorithm is correct because string reversal is a symmetric permutation. For a string of length $N$, the character at index $i$ must end up at index $N-1-i$. Our algorithm explicitly performs the swap $(i, N-1-i)$ for all $0 \le i < N/2$.

• The loop condition left < right ensures we process exactly the first half of the indices.
• By swapping s[i] with s[N-1-i], we place both characters in their correct final positions simultaneously.
• Since every pair is swapped exactly once, the entire string is reversed.

Pattern Reuse Notes

The Two Pointers pattern used here is foundational. Understanding how to manipulate array boundaries allows you to solve more complex variations:

• LeetCode 151: Reverse Words in a String - Requires reversing the entire string (like 344) and then reversing individual words, or vice-versa.
• LeetCode 345: Reverse Vowels of a String - Applies the same converging pointer logic but adds a condition: pointers only stop and swap if both point to vowels.
• LeetCode 541: Reverse String II - Applies the reversal logic in fixed-size blocks (every $2k$ characters), requiring careful index management.

Reference Implementation

C++ Solution for LeetCode 344

1class Solution {
2public:
3    void reverseString(vector<char>& s) {
4        int left = 0;
5        int right = s.size() - 1;
6        
7        // Loop until the two pointers meet in the middle
8        while (left < right) {
9            // Swap characters at the left and right pointers
10            char temp = s[left];
11            s[left] = s[right];
12            s[right] = temp;
13            
14            // Move pointers inward
15            left++;
16            right--;
17        }
18    }
19};

Java Solution for LeetCode 344

1class Solution {
2    public void reverseString(char[] s) {
3        int left = 0;
4        int right = s.length - 1;
5        
6        // Loop until the two pointers meet in the middle
7        while (left < right) {
8            // Swap characters at the left and right pointers
9            char temp = s[left];
10            s[left] = s[right];
11            s[right] = temp;
12            
13            // Move pointers inward
14            left++;
15            right--;
16        }
17    }
18}

Python Solution for LeetCode 344

1class Solution:
2    def reverseString(self, s: List[str]) -> None:
3        """
4        Do not return anything, modify s in-place instead.
5        """
6        left = 0
7        right = len(s) - 1
8        
9        # Loop until the two pointers meet in the middle
10        while left < right:
11            # Swap characters using tuple unpacking
12            s[left], s[right] = s[right], s[left]
13            
14            # Move pointers inward
15            left += 1
16            right -= 1