151. Reverse Words in a String
Model: qwen3.5:9b
Topics: String
FAANG asked: 1
Acceptance rate: 24.1%
Problem Breakdown
We are given a string s containing words separated by one or more space characters. The goal is to return the same words in reverse order (last word becomes first). Crucially, we must normalize whitespace: any leading/trailing spaces and multiple consecutive internal spaces should be collapsed into exactly single spaces between words in the output.
Inputs: A string s containing English letters, digits, and spaces.
Outputs: A new string with reversed word order and normalized spacing (single space separators).
Constraints & Edge Cases to Consider:
- Leading/trailing whitespace must be stripped from the result.
- Multiple consecutive spaces between words in input become a single space in output.
- The problem guarantees at least one word exists, so we don’t need to handle an empty string case specifically (though robust code handles it).
Intuition
The core challenge here is tokenization and normalization rather than just reversing characters.
- Naive Approach: One might think of iterating through the character array manually: skip spaces until a letter, collect letters into a word buffer, then when hitting a space or end-of-string, store that word in a list.
- Why it’s insufficient (or suboptimal): While manual iteration is O(N), implementing this logic from scratch introduces complexity regarding state management (is current char part of a word? did we just skip spaces?). It also increases the risk of bugs with edge cases like multiple consecutive spaces or leading whitespace.
- Key Insight: In Python, string methods abstract away low-level memory handling. The
split()method without arguments automatically handles all whitespace normalization rules defined in the problem (treating any sequence of whitespace as a single delimiter and ignoring empty strings resulting from it). This allows us to focus on the logic: extract tokens -> reverse order -> reconstruct string.
Approach
- Tokenization: Use
s.split()which splits by any whitespace run, automatically stripping leading/trailing spaces and collapsing multiple internal spaces into one separator conceptually (by ignoring empty strings in the resulting list). - Reversal: Reverse the order of tokens using Python slicing (
[::-1]). This is efficient as it creates a new view without copying data immediately until joined. - Concatenation: Use
' '.join()to reconstruct the string with exactly one space between each token.
This approach leverages built-in optimizations for whitespace handling, ensuring correctness across all edge cases (like ” hello world ”) in O(N) time. For languages like C++ or Java where strings are mutable arrays, we would need a two-pass strategy: reverse characters then swap words around delimiters to achieve the follow-up’s O(1) space requirement relative to input size.
Complexity Analysis
- Time Complexity:
- We iterate through the string once during splitting and join operations are linear with respect to output length.
- Space Complexity: in Python context.
split()creates a list of words (proportional to number of characters).' '.join()creates the final string buffer.- Note: In an interview follow-up asking for “in-place” O(1) extra space, this solution would not satisfy that constraint because Python strings are immutable and
splitallocates new memory. However, it is optimal given language constraints unless using a mutable character array approach (like in C++).
Solution
def reverse_words(s: str) -> str:
# split() handles multiple spaces as one delimiter
# and automatically strips leading/trailing whitespace by default behavior
words = s.split()
# Reverse the list of tokens using slicing with step -1
reversed_words = words[::-1]
# Join them back together with a single space separator
return ' '.join(reversed_words)
Edge Cases Handled
- Leading/Trailing Spaces:
s.split()ignores these automatically, so the output never starts or ends with spaces. - Multiple Internal Spaces: Consecutive whitespace characters are treated as a single delimiter by default split behavior; no empty strings appear in the list to be reversed.
- Single Word Input: The logic holds (list length 1 -> reverse is same -> join returns word).
- Input with Digits/Chars:
split()treats any non-whitespace sequence as a valid token, so digits and mixed alphanumeric words are preserved correctly without modification.