Reverse Words in a String

Problem

Given a string s, return a string containing the same words in reverse order, separated by single spaces.

A word is a maximal run of non-space characters. The input may have leading spaces, trailing spaces, or multiple spaces between words. The output must have no leading or trailing spaces and exactly one space between adjacent words.

Examples

Example 1

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

Four words, order reversed.

Example 2

Input:  s = "  hello world  "
Output: "world hello"

Leading and trailing spaces are stripped.

Example 3

Input:  s = "a good   example"
Output: "example good a"

The triple space collapses to a single separator.

Constraints

• 1 <= s.length <= 10^4
• s consists of letters, digits, and spaces ' '.
• s contains at least one word.
• Follow-up: if strings were mutable in your language, could you do it in place with O(1) extra space?

Think about it first

TL;DR

Split/reverse/join is O(n) time and O(n) space. The interview-grade answer is reverse-the-whole-buffer-then-reverse-each-word: O(n) time and O(1) extra space on a mutable buffer.

Approach 1 — Built-ins (split, reverse, join)

Python’s str.split() with no argument already handles leading, trailing, and repeated spaces, so the whole task is three standard operations.

def reverseWords(s: str) -> str:
    return " ".join(reversed(s.split()))

Complexity: O(n) time, O(n) space. This is accepted, but it shows no algorithmic content and cannot answer the O(1)-space follow-up.

Approach 2 — Two pointers scanning from the end

The insight: the output is the words read right-to-left, so scan backward with two pointers: end sits on the last character of a word, and the inner loop walks i back to the character before the word. Emitting words in scan order produces the reversed order directly, with no separate reversal step and no split.

def reverseWords(s: str) -> str:
    parts: list[str] = []
    i = len(s) - 1
    while i >= 0:
        while i >= 0 and s[i] == " ":   # skip trailing/gap spaces
            i -= 1
        if i < 0:
            break
        end = i
        while i >= 0 and s[i] != " ":   # walk to word start
            i -= 1
        parts.append(s[i + 1 : end + 1])
    return " ".join(parts)

Walkthrough on s = " hello world " (indices 0–14):

1. i = 14: skip spaces down to i = 12 ('d'). end = 12; walk back to i = 7 (space). Emit s[8:13] = "world".
2. Skip the space at 7 → i = 6 ('o'). end = 6; walk back past i = 2 ('h') to i = 1 (space). Emit s[2:7] = "hello".
3. Skip spaces at 1, 0 → i = -1, outer loop exits.

parts = ["world", "hello"] gives "world hello".

Complexity: O(n) time (each character is visited a constant number of times), O(n) space for the output, which is unavoidable with immutable strings.

Approach 3 — Reverse the whole buffer, then reverse each word (O(1)-space follow-up)

The insight: reversing the entire character array reverses the word order and the spelling of every word; reversing each word again fixes the spelling while keeping the new order. With an in-place space-compaction pass first, everything runs in O(1) extra space on a mutable buffer. In Python we simulate the buffer with a list of chars, so it is O(n) here, but the technique is genuinely in-place in C++/Java/Rust.

def reverseWords(s: str) -> str:
    buf = list(s)

    # 1) compact spaces in place: single separators, no lead/trail
    write = 0
    read = 0
    n = len(buf)
    while read < n:
        while read < n and buf[read] == " ":
            read += 1
        if read >= n:
            break
        if write > 0:
            buf[write] = " "
            write += 1
        while read < n and buf[read] != " ":
            buf[write] = buf[read]
            write += 1
            read += 1
    del buf[write:]

    def rev(lo: int, hi: int) -> None:
        while lo < hi:
            buf[lo], buf[hi] = buf[hi], buf[lo]
            lo += 1
            hi -= 1

    # 2) reverse everything
    rev(0, len(buf) - 1)

    # 3) reverse each word back
    start = 0
    for i in range(len(buf) + 1):
        if i == len(buf) or buf[i] == " ":
            rev(start, i - 1)
            start = i + 1

    return "".join(buf)

Walkthrough on s = "a good example":

1. Compaction: buf = "a good example" (the triple space collapses).
2. Full reversal: "elpmaxe doog a".
3. Per-word reversal: "elpmaxe" becomes "example", "doog" becomes "good", "a" stays "a", giving "example good a".

Complexity: O(n) time. Compaction is one pass, and every character is swapped at most twice across the two reversal phases. O(1) extra space on a mutable buffer (O(n) in Python only because strings are immutable).

Common pitfalls

• Trusting naive splitting: s.split(" ") (with an explicit separator) produces empty strings for repeated spaces; only argument-less split() collapses them.
• Off-by-one slicing in the backward scan: after walking i past the word start, the word is s[i + 1 : end + 1] — both +1s are easy to drop.
• Separator handling in the in-place version: writing the space before each word (guarded by write > 0) avoids a trailing space that would otherwise need a trim pass.
• Reversing words before compacting: extra spaces change word boundaries; compact first so phases 2–3 see clean single separators.

Pattern takeaway

Two reusable moves live in this problem. First, scanning with a pointer pair that finds boundaries (end of word, start of word) is how you tokenize without library calls. Second, the reverse-then-reverse-segments identity turns “reorder blocks in place” into pure reversals. The same identity powers in-place array rotation, so it is worth remembering for any O(1)-space rearrangement follow-up.