Free lesson · DSA Mastery - Interview Prep, End to End

Reverse Words in a String

Medium8 min readdsastrings

Reverse Words in a String

Reverse Words in a String is the string version of the reverse trick from Rotate Array. The naive approach (split, reverse the array, join) works but uses O(n) auxiliary space. The clever O(1) auxiliary space approach uses two reversals - reverse the whole string, then reverse each word individually - combined with careful boundary handling.

The problem also has a parsing dimension: input strings may have leading, trailing, or interior whitespace that must be normalized. Getting both the reversal and the normalization right in a single in-place pass is what makes this problem genuinely instructive.

The Problem

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

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

Example 2:

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

Explanation: Leading/trailing spaces removed. Two words reversed.

Example 3:

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

Explanation: Multiple spaces collapsed to single space.

Constraints:

• 1 <= s.length <= 10^4
• s contains English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

Follow-up: If the string data type is mutable (e.g., a char array in C/C++), could you do it in-place with O(1) extra space?

Approach

Two approaches worth knowing.

Approach 1: Split + Reverse + Join (the obvious solution)

public static String reverseWordsObvious(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder result = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        result.append(words[i]);
        if (i > 0) result.append(' ');
    }
    return result.toString();
}

This is O(n) time and O(n) space. Clean, idiomatic Java. Most interviews would accept this.

Approach 2: Two-Reversal + In-Place Cleanup (the in-place version)

For the follow-up (char array, in-place):

1. Normalize spaces. Compact the array so there's a single space between words and no leading/trailing spaces.
2. Reverse the entire string. Now the words are in reverse order, but each word is also internally reversed.
3. Reverse each word individually. Words are now in correct order.

This is O(n) time and O(1) auxiliary space (the result is in the input buffer).

graph TD
    A["Step 1: Compact spaces"] --> B["Step 2: Reverse entire string"]
    B --> C["Step 3: Reverse each word"]
    C --> D["Done"]
    
    style A fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the three-step in-place approach. First we compact spaces, removing leading and trailing spaces and collapsing multiple internal spaces to single spaces. Then we reverse the entire string. Then we reverse each individual word. The combined operations produce the words in reversed order with normalized spacing.

The reverse-twice trick works because reversing the whole string puts words in reverse order (and each word backwards), and then reversing each word brings the words to forward orientation while preserving their reverse order.

For the basic Java problem (immutable strings), Approach 1 is fine. For the in-place follow-up, Approach 2 is the answer.

Code Implementation

public static String reverseWords(String s) {
    char[] arr = s.toCharArray();
    int n = arr.length;
    
    // Step 1: Compact spaces (in-place)
    int writeIdx = 0;
    int readIdx = 0;
    
    // Skip leading spaces
    while (readIdx < n && arr[readIdx] == ' ') readIdx++;
    
    while (readIdx < n) {
        // Copy a word
        while (readIdx < n && arr[readIdx] != ' ') {
            arr[writeIdx++] = arr[readIdx++];
        }
        // Skip spaces
        while (readIdx < n && arr[readIdx] == ' ') readIdx++;
        // Add single space if more words to come
        if (readIdx < n) arr[writeIdx++] = ' ';
    }
    
    int newLength = writeIdx;
    
    // Step 2: Reverse the whole compacted region
    reverse(arr, 0, newLength - 1);
    
    // Step 3: Reverse each word
    int wordStart = 0;
    for (int i = 0; i <= newLength; i++) {
        if (i == newLength || arr[i] == ' ') {
            reverse(arr, wordStart, i - 1);
            wordStart = i + 1;
        }
    }
    
    return new String(arr, 0, newLength);
}

private static void reverse(char[] arr, int left, int right) {
    while (left < right) {
        char temp = arr[left];
        arr[left++] = arr[right];
        arr[right--] = temp;
    }
}

// Usage:
// System.out.println(reverseWords("the sky is blue"));        // "blue is sky the"
// System.out.println(reverseWords("  hello world  "));        // "hello world"
// System.out.println(reverseWords("a good   example"));       // "example good a"

This Java code implements Reverse Words with the three-step in-place approach. Step one compacts spaces by reading characters with one pointer and writing them with another, preserving exactly one space between words. Step two reverses the entire compacted region. Step three reverses each word individually by tracking word boundaries via spaces. The function returns a string from the cleaned char array.

The reverse helper is the same one from Reverse String (topic 7.1). Reuse is the point.

For interviews where the simpler approach is acceptable, the split-reverse-join version is fine. Show the in-place version when asked about the follow-up.

Walkthrough

Trace on s = " hello world ". The original char array has length 15: two leading spaces, "hello", one separating space, "world", two trailing spaces.

Step 1: Compact Spaces

Initial: arr = [' ', ' ', 'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', ' ', ' '], n = 15.

Skip leading spaces: readIdx advances from 0 to 2.

Outer iteration 1:
  Copy word "hello":
    arr[0]='h', arr[1]='e', arr[2]='l', arr[3]='l', arr[4]='o'. writeIdx=5, readIdx=7.
  Skip spaces: readIdx advances from 7 to 8.
  More words remain (readIdx < n), so add separator: arr[5]=' '. writeIdx=6.

Outer iteration 2:
  Copy word "world":
    arr[6]='w', arr[7]='o', arr[8]='r', arr[9]='l', arr[10]='d'. writeIdx=11, readIdx=13.
  Skip spaces: readIdx advances from 13 to 15.
  No more words (readIdx == n), so no separator added.

newLength = 11.
arr[0..10] = "hello world". Positions 11..14 hold leftover garbage from before.

Step 2: Reverse the Whole Compacted Region

reverse(arr, 0, 10) on "hello world":
  Swap arr[0]='h' and arr[10]='d'.
  Swap arr[1]='e' and arr[9]='l'.
  Swap arr[2]='l' and arr[8]='r'.
  Swap arr[3]='l' and arr[7]='o'.
  Swap arr[4]='o' and arr[6]='w'.
  arr[5]=' ' stays put (mirror of itself).

arr[0..10] = "dlrow olleh".

Step 3: Reverse Each Word

Walk i from 0 to newLength = 11, with wordStart = 0.

i=0..4: 'd','l','r','o','w' - non-space, no action.
i=5: arr[5]=' '. Reverse arr[wordStart..i-1] = arr[0..4] = "dlrow" → "world".
     wordStart = 6.
     arr[0..10] now = "world olleh".

i=6..10: 'o','l','l','e','h' - non-space, no action.
i=11: i == newLength (loop sentinel). Reverse arr[wordStart..i-1] = arr[6..10] = "olleh" → "hello".
     arr[0..10] now = "world hello".

Loop exits.

Final result: "world hello" - the two words swapped, with leading/trailing spaces stripped and the single separator preserved.

Trace on s = "a good example" (the multi-space case, length 16):

Step 1 (compact): "a good example", newLength = 14.
  - The triple space between "good" and "example" collapses to one.

Step 2 (reverse all): "a good example" → "elpmaxe doog a".

Step 3 (reverse each word):
  - arr[0..6] = "elpmaxe" → "example".
  - arr[8..11] = "doog" → "good".
  - arr[13..13] = "a" → "a" (single character, no-op).

Final: "example good a".

Three words reversed in order, internal multi-spaces normalized to single spaces.

Complexity Analysis

Why It Is O(n) Time

Step 1 (compaction) does at most n read-write operations: O(n). Step 2 (reverse whole) is O(n). Step 3 (reverse each word) touches each character at most twice (once in the reverse, once in the boundary scan): O(n). Total: O(n).

Why It Is O(1) Space (In-Place Version)

The compaction is in-place. The reversals are in-place. The only auxiliary memory is loop counters and a temp variable for swaps. The output is built in the input array.

The new String(arr, 0, newLength) allocation at the end is for returning the result; we could avoid it if the API required modifying a char array.

Variations & Follow-ups

What if the string is in-place mutable (e.g., C/C++ char array)?

The three-step in-place algorithm above is the answer. O(1) auxiliary space.

What if you needed to reverse characters in each word but keep word order?

Different problem - "Reverse Words in a String III" (LeetCode #557). Don't reverse the whole string; just reverse each word's characters. Single pass.

What if you needed to preserve original spacing?

Reverse the order of words but keep multi-spaces between them. The compaction step changes - you'd preserve groups of spaces as "spacer tokens" and reverse the sequence of [word, spacer, word, spacer, ...].

What if the words could be Unicode?

Use grapheme-cluster-aware string operations. The algorithm structure is the same, but the iteration unit changes from char to grapheme.

What about edge cases?

• Empty string after stripping (e.g., " "): Problem says at least one word exists, so this won't happen. If it did, newLength would be 0, and the algorithm would return an empty string.
• Single word ("hello"): Compaction copies it. Reversal makes it "olleh". Reversing the single word makes it "hello" again. Output: "hello". Correct.
• All same character ("aaa"): Stays the same throughout. Correct.
• Single character ("a"): Single word, single char. Output: "a".

Common Interview Pitfalls

• Forgetting to handle multiple internal spaces. "a b" should become "b a", not "b a". Compaction must collapse runs of spaces to single spaces.
• Forgetting trailing/leading spaces. They must be stripped.
• Off-by-one in word reversal. The word at positions [wordStart, i-1] (inclusive) - note the i-1. Using [wordStart, i] includes the space character.
• Adding a space after the last word. The check if (readIdx < n) after compacting a word ensures we only add a space if there's more content to come.
• Using Java's String.split with no argument. split("\\s+") collapses spaces correctly. split(" ") would produce empty strings between multiple spaces. Use the regex version or trim first.

Why This Problem Matters

Reverse Words demonstrates the reverse-twice trick in a string-parsing context. The same idea (reverse the whole, then reverse parts) appeared in Rotate Array - there it produced cyclic rotation; here it produces word-order reversal.

The pattern reappears in:

• String rotation detection - check if t is a rotation of s by searching for t in s + s.
• Cyclic permutation reversal - generalization of array rotation.
• In-place layout transformations - many "rearrange in some pattern" problems can use multi-step reversal.

Plus, the in-place compaction with two pointers (read/write) is the same skeleton from Move Zeroes (topic 6.2), now applied to character data. The two patterns combine here naturally.

The next topic, One Edit Distance, introduces a different kind of comparison - counting differences between strings with a careful linear scan.

Back to DSA Mastery - Interview Prep, End to End