Reverse Words in a String

Difficulty: Medium
Topics: Two Pointers, String
Link: https://leetcode.com/problems/reverse-words-in-a-string/

Problem Description

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:


Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:


Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:


Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

**Follow-up:**If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Solution

1. Problem Deconstruction

Technical Restatement: Given a string s consisting of English letters, digits, and spaces, process the string to:

Identify contiguous sequences of non-space characters (words)
Reverse their original order
Concatenate them with exactly one space between adjacent words
Eliminate all leading/trailing spaces and reduce internal multiple spaces to single spaces
Return the transformed string while handling edge cases of extreme spacing

Beginner-Friendly Version: Imagine you have a sentence where words might have extra spaces at the beginning, end, or between words. Your task is to:

Find all the actual words (groups of letters/numbers)
Put them in reverse order
Join them back together with just one space between each word
Make sure there are no spaces at the start or end

Mathematical Formulation: Let $s$ be a string of length $n$ where $s[i]$ represents the $i$ -th character. Define:

Word boundaries: indices where $ParseError: KaTeX parse error: Double superscript at position 13: s[i] \neq ' '̲$ and ( $i=0$ or $ParseError: KaTeX parse error: Double superscript at position 12: s[i-1] = ' '̲$ )
Word endpoints: maximal sequences where $ParseError: KaTeX parse error: Double superscript at position 41: …], s[j] \neq ' '̲$
Output: concatenate words in reverse order with mapping function $ParseError: KaTeX parse error: Double superscript at position 27: …-1}) = w_k + ' '̲ + w_{k-1}$

Constraint Analysis:

$1 \leq n \leq 10^4$ : Rules out O(n²) solutions like repeated string concatenation
English letters/digits/spaces: No special Unicode handling required
At least one word: Eliminates empty output edge case
Multiple space handling: Cannot simply split/join without normalization
Leading/trailing spaces: Must trim results carefully

Hidden Edge Cases:

Single word input (“hello” → “hello”)
All spaces except one word (" word " → “word”)
Alternating single characters (“a b c d” → “d c b a”)
Maximum length with minimal words (10,000 characters with 2 words)

2. Intuition Scaffolding

Real-World Metaphor (Book Printing): Imagine you have a manuscript with inconsistent spacing between words. You need to:

Scan the text to identify individual words (like an editor marking paragraphs)
Reverse the chapter order while maintaining word integrity
Typeset the final version with professional spacing standards

Gaming Analogy (Inventory Reorganization): Like sorting your RPG inventory where items (words) are scattered randomly in chests (spaces). You must:

Identify all valid items (non-space sequences)
Rearrange them in reverse acquisition order
Store them in a new chest with optimal space between items

Math Analogy (Set Reversal): Treat words as elements in an ordered set $W = {w_1, w_2, ..., w_k}$ . The operation is constructing a new ordered set $W' = {w_k, w_{k-1}, ..., w_1}$ with a distance metric of exactly 1 space between adjacent elements.

Common Pitfalls:

Using built-in split/reverse/join without space handling - fails on multiple spaces
Reversing character-by-character - destroys word integrity
Tracking word boundaries incorrectly - off-by-one errors at string ends
Adding extra space at end - fails trailing space requirement
Using O(n) extra space unnecessarily - violates follow-up requirement

3. Approach Encyclopedia

Approach 1: Built-in Functions (Python)

def reverseWords(s: str) -> str:
    return ' '.join(s.split()[::-1])

Logic: Split on whitespace (handles multiple spaces), reverse list, join with single spaces
Time Complexity: O(n) for split + O(k) for reverse + O(n) for join = O(n)
Space Complexity: O(n) for storing word list and output string

Approach 2: Deque-based Reconstruction

from collections import deque
def reverseWords(s: str) -> str:
    left, right = 0, len(s) - 1
    # Remove leading spaces
    while left <= right and s[left] == ' ':
        left += 1
    # Remove trailing spaces
    while left <= right and s[right] == ' ':
        right -= 1
        
    d, word = deque(), []
    # Process words between left and right pointers
    while left <= right:
        if s[left] == ' ' and word:
            d.appendleft(''.join(word))
            word = []
        elif s[left] != ' ':
            word.append(s[left])
        left += 1
    d.appendleft(''.join(word))
    
    return ' '.join(d)

Logic: Manual word boundary detection with deque for O(1) left insertion
Time Complexity: O(n) single pass with O(1) deque operations
Space Complexity: O(n) for deque and word storage

Approach 3: In-place Reverse (Follow-up)

def reverseWords(s: str) -> str:
    # Convert to list for mutability
    chars = list(s)
    
    def reverse_range(start, end):
        while start < end:
            chars[start], chars[end] = chars[end], chars[start]
            start += 1
            end -= 1
    
    # Step 1: Reverse entire string
    reverse_range(0, len(chars) - 1)
    
    # Step 2: Reverse individual words and clean spaces
    start = i = 0
    for j in range(len(chars) + 1):
        if j == len(chars) or chars[j] == ' ':
            if i > start:  # Non-empty word found
                reverse_range(start, i - 1)
                if j < len(chars):
                    chars[i] = ' '
                    i += 1
                start = i
            else:
                start = j + 1
        else:
            chars[i] = chars[j]
            i += 1
    
    return ''.join(chars[:i]).strip()

Logic: Three-phase in-place transformation
Time Complexity: O(n) for multiple passes
Space Complexity: O(1) excluding input modification (meets follow-up)

Visualization (In-place Approach):

Initial:  "  hello   world  "
Phase 1:  "  dlrow   olleh  "  (full reverse)
Phase 2:  "world hello"         (word reverse + space cleanup)

4. Code Deep Dive

Optimal Solution (In-place Python):

class Solution:
    def reverseWords(self, s: str) -> str:
        # Convert to list for in-place modification
        chars = list(s)
        n = len(chars)
        
        def reverse(l, r):
            """Reverse characters between indices l and r inclusive"""
            while l < r:
                chars[l], chars[r] = chars[r], chars[l]
                l += 1
                r -= 1
        
        # Step 1: Reverse entire string to get words in correct positions
        reverse(0, n - 1)
        
        # Step 2: Reverse individual words and remove extra spaces
        i = start = 0  # i: write pointer, start: word start
        for j in range(n + 1):  # Include virtual end position
            if j == n or chars[j] == ' ':
                # Found word boundary
                if start < j:  # Non-empty word exists
                    # Reverse the word to original order
                    reverse(start, j - 1)
                    # Copy word to current write position
                    for k in range(start, j):
                        chars[i] = chars[k]
                        i += 1
                    # Add space if not last word
                    if j < n:
                        chars[i] = ' '
                        i += 1
                start = j + 1  # Move to next word start
        
        # Return trimmed result (remove trailing space if present)
        return ''.join(chars[:i-1]) if i > 0 and chars[i-1] == ' ' else ''.join(chars[:i])

Line-by-Line Analysis:

Lines 3-4: Convert to list for O(1) character swapping
Lines 6-10: Classic two-pointer reversal algorithm
Line 13: Initial full reversal places words in target positions (but reversed)
Lines 16-28: Core state machine tracking word boundaries and write positions
Line 18: Virtual end position handles final word uniformly
Lines 22-25: Word reversal and compaction in single pass
Line 32: Final trim handles edge case of trailing space in output

Edge Case Handling:

Example 2 (" hello world "): Leading/trailing spaces skipped by start pointer logic
Example 3 (“a good example”): Multiple spaces collapsed by only writing after words
Single word: Loop maintains word order without extra spaces

5. Complexity War Room

Hardware-Aware Analysis:

At maximum input size (10^4 characters):
- Character list uses ~80KB memory (fits in L2/L3 cache)
- Single pass algorithm benefits from cache locality
- In-place modification avoids heap allocations

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Built-in	O(n)	O(n)	10/10	✅ Quick solution
Deque	O(n)	O(n)	8/10	✅ Demonstrates algo knowledge
In-place	O(n)	O(1)*	6/10	✅ Follow-up requirement

*Excluding input storage modification

6. Pro Mode Extras

Variants Section:

Variant 1 (Reverse Words II): Reverse words without trimming spaces
- Solution: Modify in-place approach to preserve space counts
Variant 2 (Reverse Words III): Reverse characters within words but maintain word order
- Solution: Apply word-level reversal without reordering words
Variant 3 (Circular Reverse): Rotate words by k positions
- Solution: Combine reversal techniques with modular arithmetic

Interview Cheat Sheet:

First Mention: Always state time/space complexity before coding
Clarify: Ask about string mutability constraints immediately
Edge Cases: Explicitly list “all spaces”, “single word”, “multiple internal spaces”
Optimization Path: Start with built-in → manual → in-place to demonstrate progression
Testing Strategy: Suggest testing with extreme spacing patterns

#151 - Reverse Words in a String