LeetCode 151 – Reverse Words in a String

Reverse Words in a String is one line in Python and a genuine exercise in Java, which is exactly what makes it a good interview question: the one-liner is correct, and the follow-up asking for O(1) space is where the actual technique lives — reverse everything, then reverse each word back.

The problem

Given a string of words separated by spaces, reverse the order of the words. The result must have a single space between words and no leading or trailing spaces.

"the sky is blue"       -> "blue is sky the"
"  hello world  "       -> "world hello"       spaces trimmed
"a good   example"      -> "example good a"    runs collapsed to one space
"  "                    -> ""
"single"                -> "single"

Note what is not asked: the characters within a word stay in order. "blue" does not become "eulb". That distinction is the whole reason the two-reversal trick works.

The straightforward answer

Split on whitespace, reverse the list, join with a single space. split() with no argument discards empty pieces, so the trimming and the collapsing come free — the same property Length of Last Word relies on.

It is O(n) time and O(n) space. Give it, then say "if the input were a mutable character array I could do this in place", which is the follow-up.

Reverse twice

"the sky is blue"

1. reverse the whole thing    "eulb si yks eht"
                               words are in the RIGHT order, spelled backwards

2. reverse each word          "blue is sky the"

Two reversals. The first fixes the word order and breaks the spelling; the second fixes the spelling and leaves the order alone, because reversing a word in place cannot move it. It is one of those tricks that is obvious in hindsight and worth being able to produce on demand.

Handling the spaces is the fiddly part rather than the reversing. Done in place, it needs a third pass that compacts runs of spaces and trims the ends — which is where most of the code goes.

Java

class Solution {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();

        int length = compactSpaces(chars);   // trim and collapse, in place
        reverse(chars, 0, length - 1);       // whole string: word order now correct

        // Reverse each word back, so the letters read forwards again.
        int start = 0;
        for (int end = 0; end <= length; end++) {
            if (end == length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }

        return new String(chars, 0, length);
    }

    /** Removes leading, trailing and repeated spaces. Returns the new length. */
    private int compactSpaces(char[] chars) {
        int write = 0;

        for (int read = 0; read < chars.length; read++) {
            if (chars[read] != ' ') {
                // One space before every word except the first.
                if (write != 0) chars[write++] = ' ';
                while (read < chars.length && chars[read] != ' ') {
                    chars[write++] = chars[read++];
                }
            }
        }

        return write;
    }

    private void reverse(char[] chars, int lo, int hi) {
        while (lo < hi) {
            char tmp = chars[lo];
            chars[lo++] = chars[hi];
            chars[hi--] = tmp;
        }
    }
}

compactSpaces writes a separator before each word rather than after, which is what makes the trailing space impossible — there is no cleanup pass. The write != 0 test is what suppresses it for the first word.

The word-reversal loop runs to end == length inclusive so the final word is reversed without a duplicated block after the loop. Sentinel-style loop bounds like that are worth reaching for; the alternative is an extra copy of the body.

Strings are immutable in Java, so this is only genuinely O(1) extra space once you have the char[]. Say that rather than claiming constant space for a method that starts with toCharArray.

Python

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

s.split() with no argument splits on runs of whitespace and drops empties, so " a b " gives ["a", "b"] — leading, trailing and repeated spaces all handled by one call. s.split(" ") would produce empty strings and break it, which is the difference worth knowing.

Python strings are immutable too, so the in-place version is not available without converting to a list. If asked, do exactly that and write the Java algorithm — but say up front that the one-liner is what you would ship.

Complexity

Each character is touched a constant number of times — once to compact, once in the full reversal, once in its word's reversal. Three passes is still linear, and saying "three passes, still O(n)" is better than leaving the interviewer to wonder whether you noticed.

The pattern

Double reversal is a small, reusable idea. Rotate Array (189) rotates by k with exactly the same move: reverse the whole array, then reverse the first k and the rest separately. Reverse Words in a String II (186) is this problem handed a char[] directly, which removes the excuse for the split version.

The general shape: when an operation is hard to do directly but its inverse composes, look for two cheap reversals that cancel in the right places.

What the interviewer is checking

• That word order reverses but spelling does not.
• Leading, trailing and repeated spaces — all three.
• That split() handles them and split(" ") does not.
• The two-reversal trick when constant space is asked for.
• That you write the separator before each word, so no trailing space needs removing.
• A whitespace-only string returning "", and a single word.
• That immutable strings mean "in place" starts with a conversion.