Problem Description

You are given a string s that contains words separated by spaces. Your task is to reverse the order of these words and return them as a single string.

A word is defined as any sequence of characters that doesn't contain spaces. Words in the input string are separated by one or more spaces.

The key requirements are:

• Extract all words from the input string
• Reverse their order (last word becomes first, second-to-last becomes second, etc.)
• Join them back together with exactly one space between each word
• Remove any extra spaces (leading, trailing, or multiple spaces between words)

For example:

• Input: " hello world " → Output: "world hello"
• Input: "the sky is blue" → Output: "blue is sky the"
• Input: " Bob Loves Alice " → Output: "Alice Loves Bob"

The solution uses two pointers to identify word boundaries:

• Pointer i skips over spaces to find the start of each word
• Pointer j moves from the start of a word to find where it ends (next space or end of string)
• Each identified word s[i:j] is added to a list
• After collecting all words, the list is reversed using words[::-1]
• Finally, the reversed words are joined with single spaces using " ".join()

This approach handles all edge cases including multiple consecutive spaces, leading/trailing spaces, and ensures the output has clean formatting with single spaces between words.

Intuition

The most straightforward way to reverse words is to first extract all the words, then reverse their order. Since we need to handle irregular spacing (multiple spaces, leading/trailing spaces), we can't simply use split() and join() blindly - we need more control over the parsing process.

The key insight is that we need to identify where each word starts and ends. We can think of this as a state machine with two states:

1. In a space region - we're currently looking at spaces and need to skip them
2. In a word region - we're currently inside a word and need to capture it

This naturally leads to a two-pointer approach:

• Use pointer i to track our current position in the string
• When we encounter spaces, keep moving i forward until we find a non-space character (or reach the end)
• When we find the start of a word at position i, use another pointer j to find where this word ends
• Extract the substring s[i:j] as a complete word

By collecting words in order as we scan from left to right, we get a list like ["the", "sky", "is", "blue"]. To reverse the word order, we can simply reverse this list to get ["blue", "is", "sky", "the"] using Python's slice notation words[::-1].

The final step is reconstruction. Since we've already extracted clean words without any spaces, joining them with a single space " ".join() automatically gives us the properly formatted output without any extra spaces.

This approach is intuitive because it breaks down the problem into three clear phases: parse (extract words), transform (reverse order), and reconstruct (join with single spaces).

Solution Approach

The solution implements a two-pointer technique to parse the string and extract words while handling irregular spacing. Let's walk through the implementation step by step:

1. Initialize data structures:

• Create an empty list words to store extracted words
• Set two pointers: i = 0 (current position) and n = len(s) (string length)

2. Main parsing loop: The outer while i < n loop continues until we've processed the entire string.

3. Skip spaces:

while i < n and s[i] == " ":
    i += 1

This inner loop moves pointer i forward through any consecutive spaces. It handles leading spaces, trailing spaces, and multiple spaces between words.

4. Extract word:

if i < n:  # Check if we haven't reached the end
    j = i  # Mark the start of the word
    while j < n and s[j] != " ":
        j += 1  # Find the end of the word
    words.append(s[i:j])  # Extract and store the word
    i = j  # Move i to where j stopped

Once we find a non-space character at position i, we:

• Use pointer j starting from i to find where the word ends
• The word spans from index i to j-1 (since s[j] is either a space or we've reached the end)
• Extract the substring s[i:j] and add it to our words list
• Update i to j to continue processing from where we left off

5. Reverse and join:

return " ".join(words[::-1])

• words[::-1] creates a reversed copy of the words list using Python's slice notation
• " ".join() concatenates all words with exactly one space between them

Time Complexity: O(n) where n is the length of the input string. We traverse the string once to extract words, and the join operation is also linear.

Space Complexity: O(n) for storing the words list and the output string.

This approach elegantly handles all edge cases: strings with only spaces return an empty string, and any combination of leading, trailing, or multiple spaces between words is properly normalized to single spaces in the output.

Example Walkthrough

Let's trace through the solution with the input string " the sky is blue ".

Initial Setup:

• s = " the sky is blue "
• words = [] (empty list to collect words)
• i = 0, n = 21 (string length)

First Iteration:

1. Skip leading spaces: i moves from 0 → 1 → 2 (skipping two spaces)
2. Found non-space at position 2 ('t')
3. Set j = 2, find word end: j moves 2 → 3 → 4 → 5 (stops at space)
4. Extract word: s[2:5] = "the", add to words: words = ["the"]
5. Update i = 5

Second Iteration:

1. Skip space at position 5: i moves 5 → 6
2. Found non-space at position 6 ('s')
3. Set j = 6, find word end: j moves 6 → 7 → 8 → 9 (stops at space)
4. Extract word: s[6:9] = "sky", add to words: words = ["the", "sky"]
5. Update i = 9

Third Iteration:

1. Skip spaces at positions 9-10: i moves 9 → 10 → 11
2. Found non-space at position 11 ('i')
3. Set j = 11, find word end: j moves 11 → 12 → 13 (stops at space)
4. Extract word: s[11:13] = "is", add to words: words = ["the", "sky", "is"]
5. Update i = 13

Fourth Iteration:

1. Skip spaces at positions 13-15: i moves 13 → 14 → 15 → 16
2. Found non-space at position 16 ('b')
3. Set j = 16, find word end: j moves 16 → 17 → 18 → 19 → 20 (stops at space)
4. Extract word: s[16:20] = "blue", add to words: words = ["the", "sky", "is", "blue"]
5. Update i = 20

Fifth Iteration:

1. Skip trailing space: i moves 20 → 21
2. Now i = 21 = n, exit main loop

Final Steps:

• Reverse the words list: words[::-1] = ["blue", "is", "sky", "the"]
• Join with single spaces: " ".join(["blue", "is", "sky", "the"]) = "blue is sky the"

Output: "blue is sky the"

Notice how the solution naturally handles the irregular spacing (2 leading spaces, 1 space after "the", 2 spaces after "sky", 3 spaces after "is", and 1 trailing space) and produces a clean output with exactly one space between words.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm traverses the string once using two pointers (i and j). The outer while loop moves through the entire string, and for each position, we either:

• Skip spaces: while i < n and s[i] == " "
• Extract a word: while j < n and s[j] != " "

Each character in the string is visited at most twice (once by i and once by j), making the traversal O(n). The string slicing operation s[i:j] takes O(k) time where k is the length of the word, but since the total length of all words combined cannot exceed n, the overall slicing operations sum to O(n). The final " ".join(words[::-1]) operation takes O(n) time (O(n) to reverse the list and O(n) to join the words). Therefore, the total time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses additional space for:

• The words list which stores all the words from the input string. In the worst case (when the string has no extra spaces), this stores approximately n characters worth of data: O(n)
• The reversed list words[::-1] creates a new list: O(n)
• The final joined string which is the return value: O(n)

Therefore, the total space complexity is O(n).

Common Pitfalls

1. Using split() without arguments vs. split(" ") with space

A frequent mistake is using split(" ") with an explicit space character instead of split() without arguments.

Incorrect approach:

def reverseWords(self, s: str) -> str:
    words = s.split(" ")  # Wrong!
    return " ".join(words[::-1])

Why it fails:

• split(" ") splits on single spaces only, creating empty strings when multiple spaces are encountered
• For input " hello world ", it produces: ['', '', 'hello', '', '', 'world', '', '']
• The output becomes " world hello " instead of "world hello"

Correct approach:

def reverseWords(self, s: str) -> str:
    words = s.split()  # Correct!
    return " ".join(words[::-1])

Why it works:

• split() without arguments splits on any whitespace and automatically removes empty strings
• It handles multiple spaces, tabs, newlines, and strips leading/trailing whitespace
• For the same input, it produces: ['hello', 'world']

2. Forgetting to update the pointer after finding a word

When manually parsing with two pointers, forgetting to update the main pointer can cause infinite loops.

Incorrect approach:

while i < n:
    # Skip spaces
    while i < n and s[i] == " ":
        i += 1
  
    if i < n:
        j = i
        while j < n and s[j] != " ":
            j += 1
        words.append(s[i:j])
        # Forgot to update i = j, causing infinite loop!

Solution: Always update the main pointer after extracting a word:

words.append(s[i:j])
i = j  # Critical: move i to where j stopped

3. Not checking bounds before extracting words

Attempting to extract a word without verifying that we haven't reached the string's end.

Incorrect approach:

while i < n:
    # Skip spaces
    while i < n and s[i] == " ":
        i += 1
  
    # Dangerous: i might equal n after skipping spaces
    j = i
    while j < n and s[j] != " ":  # s[i] could be out of bounds
        j += 1
    words.append(s[i:j])  # Might append empty string

Solution: Add a bounds check before processing a word:

if i < n:  # Ensure we have characters left to process
    j = i
    while j < n and s[j] != " ":
        j += 1
    words.append(s[i:j])

4. Using string concatenation instead of list for building result

Building the result by concatenating strings is inefficient and error-prone.

Inefficient approach:

result = ""
for i in range(len(words) - 1, -1, -1):
    if result:
        result += " " + words[i]  # O(n²) due to string immutability
    else:
        result = words[i]

Better approach:

return " ".join(words[::-1])  # O(n) and cleaner

The join method is more efficient because it calculates the total size needed and allocates memory once, rather than creating new string objects repeatedly.