Reverse Words in a String

LeetCode 151: Reverse Words in a String Solution & Explanation

Problem Overview

TL;DR: The optimal solution normalizes spaces, reverses the entire string to order words correctly, and then reverses each individual word to restore character order.

The problem asks us to take an input string s, which may contain leading, trailing, or multiple spaces between words, and return a new string where the words are placed in reverse order, separated by a single space. This is a classic string manipulation task often used to test understanding of array indexing and memory management.

This guide provides a detailed LeetCode 151 Solution using the Two Pointer pattern, focusing on the in-place variation highly valued in technical interviews.

Brute Force Approach for Reverse Words in a String

The naive approach relies heavily on high-level language built-ins to tokenize the string.

1. Split the string by spaces into a list of strings (tokens).
2. Filter out empty strings resulting from multiple consecutive spaces.
3. Reverse the list of tokens.
4. Join the tokens back into a single string with a space delimiter.

Pseudo-code:

function reverseWords(s):
    tokens = split(s, " ")
    clean_tokens = filter(tokens, not empty)
    reversed_tokens = reverse(clean_tokens)
    return join(reversed_tokens, " ")

Time Complexity: $O(N)$, where $N$ is the length of the string. Space Complexity: $O(N)$, to store the list of words.

Why it fails (Contextual): While this approach is acceptable for high-level scripting, it fails to demonstrate the algorithmic proficiency required for systems programming roles. It relies on allocating new memory for every word. In languages with mutable strings (like C++), or in constrained environments, the interviewer specifically looks for the O(1) extra space solution mentioned in the problem's follow-up. The brute force approach ignores the structural "in-place" challenge.

Algorithm Strategy: Two Pointer Patterns

We will implement the solution in three distinct phases to maintain clarity and handle edge cases (extra spaces) robustly.

1. Trim and Normalize Spaces (Read/Write Pointers): Use two pointers, left (write index) and right (read index). Iterate through the string with right. If s[right] is a non-space character, copy it to s[left]. If it is a space, only copy it if it's the first space after a word (ignoring leading spaces and duplicates). Finally, resize the string to length left.

2. Reverse the Whole String: Use standard two-pointer reversal (swap start and end, move inward) on the entire sanitized string.

3. Reverse Each Word: Iterate through the reversed string. Maintain a pointer start at the beginning of the current word. Move a pointer end until a space or the end of the string is found. Perform a two-pointer reversal on the substring from start to end - 1. Move start to the next word.

This strategy ensures $O(N)$ time complexity and $O(1)$ extra space (for mutable strings), satisfying all constraints and the follow-up.

Execution Flow

1. Variable Initialization:

   • Initialize write_ptr to 0.
   • Initialize read_ptr to 0.

2. Phase 1: Space Normalization

   • Loop read_ptr from 0 to string length.
   • Skip Leading/Multiple Spaces: If s[read_ptr] is a space and (we are at the start OR the previous copied char was a space), increment read_ptr and continue.
   • Copy Characters: Otherwise, copy s[read_ptr] to s[write_ptr]. Increment both.
   • Trailing Space Handling: After the loop, if the last character copied was a space (and string is not empty), decrement write_ptr by 1.
   • Resize: Truncate the string to size write_ptr.

3. Phase 2: Global Reversal

   • Call a helper function reverse(s, 0, length - 1) which swaps characters at both ends moving inward.

4. Phase 3: Local Word Reversal

   • Initialize start = 0.
   • Loop end from 0 to length.
   • If s[end] is a space or end is equal to length:
     • Call reverse(s, start, end - 1).
     • Set start = end + 1.

5. Return: The modified string.

Proof of Correctness

The correctness relies on the property of double reversal. Let a string $S$ consists of words $w_1, w_2, ..., w_n$. The target output is $w_n, ..., w_2, w_1$ (with corrected internal character order).

1. After space normalization, $S = w_1 \text{ } w_2 \text{ } ... \text{ } w_n$.
2. After global reversal $S^R$, the sequence of characters is reversed. The last character of $w_n$ is at index 0. The layout is effectively $w_n^R \text{ } w_{n-1}^R \text{ } ... \text{ } w_1^R$, where $w^R$ denotes a word with reversed characters.
3. Iterating through the string and reversing each segment $w_i^R$ results in $(w_i^R)^R = w_i$.
4. The final state is $w_n \text{ } w_{n-1} \text{ } ... \text{ } w_1$, which matches the requirement.

Pattern Reuse Notes

The Two Pointers - String Reversal pattern is versatile. It applies to:

• LeetCode 344: Reverse String - The foundational problem for this pattern; simple global reversal.
• LeetCode 345: Reverse Vowels of a String - Uses two pointers moving inward to swap specific characters.
• LeetCode 541: Reverse String II - Applies the reversal logic in fixed steps (every $2k$ characters).

Reference Implementation

C++ Solution for LeetCode 151

1#include <string>
2#include <algorithm>
3#include <vector>
4
5class Solution {
6public:
7    string reverseWords(string s) {
8        // Phase 1: Clean spaces
9        int n = s.length();
10        int write = 0;
11        
12        for (int read = 0; read < n; ++read) {
13            if (s[read] != ' ') {
14                // If not the first word, add a space before the new word
15                if (write != 0) {
16                    s[write++] = ' ';
17                }
18                
19                // Copy the word
20                int start = read;
21                while (read < n && s[read] != ' ') {
22                    s[write++] = s[read++];
23                }
24                // Determine length of word for reversal later? 
25                // No, simpler to just clean first, then reverse logic.
26                // The loop increments read, so we decrement to check next char correctly in outer loop logic
27                read--; 
28            }
29        }
30        s.resize(write);
31        
32        // Phase 2: Reverse the whole string
33        std::reverse(s.begin(), s.end());
34        
35        // Phase 3: Reverse each word
36        int start = 0;
37        for (int end = 0; end <= s.length(); ++end) {
38            // Check for end of word (space) or end of string
39            if (end == s.length() || s[end] == ' ') {
40                std::reverse(s.begin() + start, s.begin() + end);
41                start = end + 1;
42            }
43        }
44        
45        return s;
46    }
47};

Java Solution for LeetCode 151

1class Solution {
2    public String reverseWords(String s) {
3        if (s == null) return null;
4        
5        char[] a = s.toCharArray();
6        int n = a.length;
7        
8        // Phase 1: Clean spaces
9        int write = 0;
10        for (int read = 0; read < n; read++) {
11            if (a[read] != ' ') {
12                if (write != 0) {
13                    a[write++] = ' ';
14                }
15                while (read < n && a[read] != ' ') {
16                    a[write++] = a[read++];
17                }
18                read--; // Adjust for outer loop increment
19            }
20        }
21        
22        // Resize array concept (logically)
23        int length = write;
24        
25        // Phase 2: Reverse the whole sanitized portion
26        reverse(a, 0, length - 1);
27        
28        // Phase 3: Reverse each word
29        int start = 0;
30        for (int end = 0; end <= length; end++) {
31            if (end == length || a[end] == ' ') {
32                reverse(a, start, end - 1);
33                start = end + 1;
34            }
35        }
36        
37        return new String(a, 0, length);
38    }
39    
40    private void reverse(char[] a, int i, int j) {
41        while (i < j) {
42            char temp = a[i];
43            a[i] = a[j];
44            a[j] = temp;
45            i++;
46            j--;
47        }
48    }
49}

Python Solution for LeetCode 151

1class Solution:
2    def reverseWords(self, s: str) -> str:
3        # Convert to list for mutability (O(N) space)
4        # We manually implement the pattern rather than using s.split()[::-1]
5        chars = list(s)
6        n = len(chars)
7        
8        # Phase 1: Clean spaces
9        write = 0
10        read = 0
11        
12        while read < n:
13            if chars[read] != ' ':
14                # Add space if not first word
15                if write != 0:
16                    chars[write] = ' '
17                    write += 1
18                
19                # Copy word
20                while read < n and chars[read] != ' ':
21                    chars[write] = chars[read]
22                    write += 1
23                    read += 1
24            else:
25                read += 1
26        
27        # Truncate to actual size
28        chars = chars[:write]
29        
30        # Phase 2: Reverse entire list
31        self.reverse(chars, 0, len(chars) - 1)
32        
33        # Phase 3: Reverse each word
34        start = 0
35        for end in range(len(chars) + 1):
36            if end == len(chars) or chars[end] == ' ':
37                self.reverse(chars, start, end - 1)
38                start = end + 1
39                
40        return "".join(chars)
41    
42    def reverse(self, chars, left, right):
43        while left < right:
44            chars[left], chars[right] = chars[right], chars[left]
45            left += 1
46            right -= 1