Reverse Words in String: LeetCode 151 Solution Explained

content:

Struggling with string manipulation in coding interviews? LeetCode 151 challenges you to reverse words while handling extra spaces—a common pain point in technical assessments. After analyzing this DSA tutorial, I've distilled the optimal approach that balances efficiency and readability. Let's break down the proven two-step reversal technique used by competitive programmers.

Core Algorithm: Double Reversal Technique

The most efficient solution involves two strategic reversals:

1. Full string reversal: Transforms "the sky is blue" → "eulb si yks eht"
2. Per-word reversal: Corrects individual words → "blue is sky the"

Why this works:

"The first reversal positions words correctly but scrambles characters. The second pass fixes character sequences while maintaining word order—a clever O(n) time solution."

Key implementation details:

• Space handling: Skip consecutive spaces during word detection
• Edge cases: Leading/trailing spaces and all-space inputs
• In-place optimization: Possible in C++ using reference manipulation

Step-by-Step Implementation

Phase 1: Full string reversal

reverse(s.begin(), s.end());  // Standard library reversal

Phase 2: Word-by-word processing

int n = s.size(), i = 0;
string ans = "";

while (i < n) {
    string word = "";
    // Extract contiguous non-space characters
    while (i < n && s[i] != ' ') { 
        word += s[i++];
    }
    // Reverse and add valid words
    if (!word.empty()) {
        reverse(word.begin(), word.end());
        ans += (ans.empty() ? "" : " ") + word;
    }
    i++;  // Skip spaces
}
return ans;

Critical pitfalls to avoid:

1. Forgetting to skip multiple spaces
2. Missing leading/trailing space handling
3. Not checking empty words before reversal

Space-Time Complexity Analysis

Metric	Performance
Time	O(n)
Space	O(n)
Optimized	O(1) space possible with in-place modification

Real-world application:

"This technique isn't just academic—text processing libraries like Python's split() use similar logic internally. Understanding it helps optimize NLP pipelines."

Advanced Optimization

For O(1) space solutions:

1. Use dual pointers to reverse words in-place
2. Employ erase-remove idiom for space trimming:

s.erase(remove(s.begin(), s.end(), ' '), s.end());

3. Combine reversal and space trimming in single passes

Actionable Checklist

1. Test edge cases: All-spaces, single-word, leading/trailing spaces
2. Benchmark solutions: Compare library vs. manual reversal
3. Extend functionality: Preserve punctuation positions
4. Practice variations: Try reversing word order without reversing characters

Recommended Resources

• Book: "The Algorithm Design Manual" by Skiena (string manipulation section)
• Tool: LeetCode Playground for testing corner cases
• Community: LeetCode Discuss threads for language-specific optimizations

Final insight:

"While the video demonstrates a clean approach, production systems often add a third pass for Unicode handling—an essential consideration beyond ASCII."

Which optimization challenge will you tackle first? Share your target use case below!