Reverse Words in a String: Split and Join, or Fully In Place

"Reverse the words in a string" sounds like a warm-up, and in Python the first answer is one line. The interview is in what comes next: what happens to the extra spaces, why the obvious split can return empty words, and how to do it in place when the string is a mutable buffer and extra memory is not allowed. That last follow-up turns a one-liner into a neat two-step trick worth knowing.

The problem it solves

Given a sentence, return the words in reverse order. "the sky is blue" becomes "blue is sky the". The letters inside each word stay in order, and the output has exactly one space between words, with none at the start or the end, even when the input had leading, trailing or repeated spaces.

That is not the same as reversing the string. Reversing the characters gives "eulb si yks eht": the right word order, with every word spelt backwards. The task is to move whole words, not letters.

The intuition

Think of each word as a sealed box. Split the sentence into boxes, reverse the row of boxes, and put them back with one space between each pair. Nothing inside a box is touched.

In code that is three steps. split() with no argument does two jobs at once: it splits on any run of whitespace and ignores whitespace at both ends, so the messy spacing disappears before the reversal starts. Reversing the list is the familiar two-pointer walk: swap the first and last, step both pointers inward, stop when they meet. Then " ".join(words) builds the answer in one pass. Building it with += in a loop can copy the growing string on every step, which is why join is the idiom.

The follow-up asks for the same result without a list of words: the input is an array of characters, as a mutable string would be in C or C++, and you may use only O(1) extra space. The trick is to reverse twice. Reverse the whole buffer and the words land in the right order, each spelt backwards. Then reverse each word on its own, and every word reads correctly again. Before that, one pass with a read pointer and a write pointer squeezes out the extra spaces. The same two-reversal idea rotates an array in place, which is in rotate array with three reversals.

Watch it run

The animation starts from split(), which hands back four words; from there on only whole words move, and the letters inside never do. It puts one pointer at each end of the list, the same two pointers as any in-place reversal. It swaps them: only the two slots change, and the strings themselves are untouched. It steps inward, leaving sky and is as the only pair to deal with. The second swap happens with the pointers about to cross, which is n / 2 swaps for n words. Once the pointers have crossed, the list is reversed, and nothing was copied that did not have to be. The last frame is the join: one join with a single space, and the extra whitespace of the input is gone for good.

The code

The lesson's version, with the messy-spacing case and an input that is only spaces. The last line is the idiomatic Python one-liner, which does the same thing:

def reverse_words(s):
    words = s.split()                      # no argument: runs of whitespace, ends trimmed
    left, right = 0, len(words) - 1
    while left < right:                    # swap the ends, walk inward
        words[left], words[right] = words[right], words[left]
        left, right = left + 1, right - 1
    return " ".join(words)                 # one separator, one copy

print(repr(reverse_words("the sky is blue")))     # 'blue is sky the'
print(repr(reverse_words("  hello   world  ")))   # 'world hello'
print(repr(reverse_words("   ")))                 # ''
print(repr(" ".join(reversed("a good   example".split()))))   # 'example good a'

The most common bug in one line. split(" ") with an explicit separator treats every single space as a boundary, so two spaces in a row produce an empty word, and the join puts the double space straight back:

print("a  b".split(" "))                   # ['a', '', 'b']
print(repr(" ".join(reversed("a  b".split(" ")))))            # 'b  a'

The in-place version on a list of characters. Step one compacts the spaces with a read and a write pointer, step two reverses the whole buffer, step three reverses each word. The prints show the buffer after each step:

def reverse_range(chars, i, j):
    while i < j:
        chars[i], chars[j] = chars[j], chars[i]
        i, j = i + 1, j - 1

def reverse_words_in_place(chars):
    """Mutable buffer, O(1) extra space: compact the spaces, reverse all, reverse each word."""
    write = 0
    for read in range(len(chars)):         # 1. copy words left, one space between them
        if chars[read] != " ":
            if write and chars[read - 1] == " ":
                chars[write] = " "
                write += 1
            chars[write] = chars[read]
            write += 1
    del chars[write:]
    print("compacted:", "".join(chars))
    reverse_range(chars, 0, len(chars) - 1)            # 2. the whole buffer
    print("reversed: ", "".join(chars))
    start = 0
    for end in range(len(chars) + 1):                  # 3. each word back to front
        if end == len(chars) or chars[end] == " ":
            reverse_range(chars, start, end - 1)
            start = end + 1
    return "".join(chars)

print(reverse_words_in_place(list("  the sky  is blue ")))
# compacted: the sky is blue
# reversed:  eulb si yks eht
# blue is sky the

Step three on its own is the sibling problem, reversing the letters of each word while keeping the word order:

print(" ".join(w[::-1] for w in "take the next bus".split()))   # ekat eht txen sub

Checked against a brute force that scans character by character and inserts each finished word at the front of the answer. Both versions and the one-liner must agree with it on 3,000 seeded random strings full of repeated, leading and trailing spaces:

import contextlib
import io
import random

def brute(s):
    """Scan character by character; each finished word goes to the FRONT of the answer."""
    out, word = [], ""
    for ch in s + " ":
        if ch == " ":
            if word:
                out.insert(0, word)
                word = ""
        else:
            word += ch
    return " ".join(out)

random.seed(24)
ok = True
for _ in range(3000):
    s = "".join(random.choice("ab  c") for _ in range(random.randint(0, 20)))
    want = brute(s)
    ok &= reverse_words(s) == want == " ".join(reversed(s.split()))
    with contextlib.redirect_stdout(io.StringIO()):     # silence the step prints
        ok &= reverse_words_in_place(list(s)) == want
print(ok)                                  # True

The complexity

• Split and join: O(n) time for n characters. O(n) extra space for the list of words and the new string, which Python needs anyway because its strings are immutable.
• Two-pointer swap: n / 2 swaps for n words; each swap moves two references, not the letters.
• In place: O(n) time, since every character is moved a constant number of times across the three passes, and O(1) extra space on a mutable buffer.

Where it goes wrong

• Using split(" "). Repeated spaces become empty words and survive into the output.
• Reversing the characters only. The word order is right, but every word is backwards.
• Forgetting the empty result. A string of only spaces must return an empty string, not a space.
• Building the answer with +=. Correct, but it can copy the growing string on every step; collect the pieces and join once.
• An off-by-one in the word loop. The last word has no space after it, so the loop must also treat the end of the buffer as a boundary.

When it shows up in interviews

It is an easy question on its own and a warm-up for string handling in general: trimming, collapsing whitespace, and two pointers on a list. The in-place follow-up is the interesting part, because the reverse-twice idea also rotates arrays and swaps two blocks of memory without a buffer. Neighbouring questions are valid palindrome, which walks two pointers inward while skipping characters, and the general two pointers technique. The patterns cheat sheet lists two pointers with the other array and string patterns.

How to say it in an interview

"Words, not characters, move, so I split on whitespace with no argument, which also drops leading, trailing and repeated spaces. I reverse the list with two pointers swapping from both ends and join with single spaces. That is O(n) time and O(n) space, which a Python string needs anyway. If the input is a mutable character buffer and I must use constant extra space, I compact the spaces with a read and a write pointer, reverse the whole buffer, then reverse each word back, which is still O(n) time."