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 — none of that may survive in the output: no leading/trailing spaces, 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)/O(n); the interview-grade answer is the reverse-then-reverse-each-word trick, O(n) time and O(1) extra space on a mutable buffer.

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

The naive-but-idiomatic take: Python’s str.split() with no argument already handles leading, trailing, and repeated spaces, so the whole task is three standard operations.

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.split()))

Complexity: O(n) time, O(n) space. Nothing about the constraints kills this — it is accepted. What kills it is the interview: it demonstrates no algorithmic content, and it cannot answer the O(1)-space follow-up.

Approach 2 — Two pointers scanning from the end

The insight: the output is just the words read right-to-left, so scan backward with two pointers: end sits on the last character of a word, start walks back to the character before the word. Emitting words in scan order gives the reversed order for free — no post-hoc reversal, no split.

class Solution:
    def reverseWords(self, 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"] → "world hello". ✓

Complexity: O(n) time (each character visited a constant number of times), O(n) space for the output — 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. Two wrongs make a right. 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’s O(n) here, but the technique is genuinely in-place in C++/Java/Rust).

class Solution:
    def reverseWords(self, 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" → "example", "doog" → "good", "a" → "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 that powers in-place array rotation, and worth keeping on the shelf for any O(1)-space rearrangement follow-up.