☕ DSA Java Articles

Topics › Strings › Medium String Problems

Reverse every word in a string

Medium TUF ID 984 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string s containing words separated by spaces. Return a string with the words in reverse order, joined by single spaces. The input may have leading spaces, trailing spaces, or several spaces between words; none of those may appear in the output. The letters inside each word keep their order.

Constraints: 1 ≤ |s| ≤ 10^4; s contains English letters, digits and spaces, and (in the LeetCode formulation) at least one word. The Java file additionally returns "" for an input that has no words at all.

Example 1

s = "this is an amazing program"
answer = "program amazing an is this"

Example 2

s = "  hello world  "
answer = "world hello"          // leading and trailing spaces are dropped

Example 3

s = "a good   example"
answer = "example good a"       // a run of spaces becomes one space

Approach 1: Brute force, split, reverse, join

Intuition. The library can do most of the work: split(" ") cuts the string at every space, we throw away the empty pieces that runs of spaces produce, reverse the list and join with a single space. It is the shortest correct program and a fine first answer; the interviewer will then usually ask you to do it by hand.

Algorithm.

  1. Split s on " " and keep the non-empty pieces in a list.
  2. Reverse the list.
  3. Join with " ".
static String bruteForce(String s) {
    List<String> words = new ArrayList<>();
    for (String w : s.split(" ")) {
        if (!w.isEmpty()) words.add(w);
    }
    Collections.reverse(words);
    return String.join(" ", words);
}

Complexity. Time O(n): splitting, reversing and joining each touch every character or word once. Space O(n) for the pieces.

Two details of String.split matter here. Consecutive separators yield empty strings in the middle of the array ("a b" → ["a", "", "b"]), which is why the filter is needed, and trailing empty strings are discarded, so "a " → ["a"]. The empty input gives [""], which the filter removes, and join of an empty list is "".

Approach 2: Better, a stack of words

Intuition. Reversal is what a stack does for free: push the words as you meet them left to right, then pop them, and they come out right to left. Scanning by hand with two nested while loops, one skipping spaces and one consuming a word, replaces split and shows you understand the tokenising. A StringBuilder assembles the result with a space between consecutive words.

Algorithm.

  1. Set i = 0. While i < n: skip spaces; remember start; advance over non-spaces; if the range is non-empty, push s.substring(start, i).
  2. Pop until the stack is empty, appending each word and a separating space when more words remain.
static String better(String s) {
    Deque<String> stack = new ArrayDeque<>();
    int n = s.length(), i = 0;
    while (i < n) {
        while (i < n && s.charAt(i) == ' ') i++;       // skip separators
        int start = i;
        while (i < n && s.charAt(i) != ' ') i++;       // consume one word
        if (i > start) stack.push(s.substring(start, i));
    }
    StringBuilder sb = new StringBuilder(n);
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
        if (!stack.isEmpty()) sb.append(' ');
    }
    return sb.toString();
}

Complexity. Time O(n). Space O(n) for the stack of words.

Approach 3: Optimal, read the words from the right

Intuition. If we want the last word first, start reading at the end of the string. Skip trailing spaces, note where a word ends, walk left to find where it starts, and append it. Repeat until the left end is reached. Nothing is stored except the output, and each character is examined exactly once. In a language with mutable strings this would be in place; in Java the output buffer is the only allocation.

Algorithm.

  1. Set j = n - 1. While j ≥ 0:
    • Move j left over spaces. If j < 0, stop.
    • Set end = j; move j left over non-spaces. The word is s[j+1..end].
    • If the buffer is non-empty, append a space; append the word.
  2. Return the buffer.
static String optimal(String s) {
    StringBuilder sb = new StringBuilder(s.length());
    int j = s.length() - 1;
    while (j >= 0) {
        while (j >= 0 && s.charAt(j) == ' ') j--;      // skip separators from the right
        if (j < 0) break;
        int end = j;                                   // last letter of the word
        while (j >= 0 && s.charAt(j) != ' ') j--;      // j + 1 is now the first letter
        if (sb.length() > 0) sb.append(' ');
        sb.append(s, j + 1, end + 1);
    }
    return sb.toString();
}

Complexity. Time O(n): j only moves left. Space O(n) for the output only, O(1) otherwise.

sb.append(s, j + 1, end + 1) copies the character range directly into the builder without creating an intermediate String, which is why this approach does fewer allocations than the previous two.

Approach 4: The in-place variant, reverse twice

Intuition. The classic C solution works on the character array itself. Reversing the whole string puts the words in the right order but spells every word backwards; reversing each word individually then fixes the spelling. The extra spaces are handled by a preliminary “squeeze” that compacts the array with a write pointer, keeping one space after each word and finally dropping the trailing one. Java strings are immutable, so we copy to a char[] first; beyond that copy the method uses constant extra space.

Algorithm.

  1. Squeeze: walk a read index r; copy letters to the write index w; copy a space only if the previous written character is a letter. Afterwards remove a trailing space.
  2. Reverse a[0..w-1].
  3. Walk the cleaned array; at every space and at the end, reverse the word that just finished.
  4. Return new String(a, 0, w).
static String optimalInPlace(String s) {
    char[] a = s.toCharArray();
    int n = a.length;
    int w = 0;                                         // 1. squeeze: write index for the cleaned string
    for (int r = 0; r < n; r++) {
        if (a[r] == ' ') {
            if (w > 0 && a[w - 1] != ' ') a[w++] = ' ';   // keep exactly one space after a word
        } else {
            a[w++] = a[r];
        }
    }
    if (w > 0 && a[w - 1] == ' ') w--;                 // drop the separator left after the last word
    reverse(a, 0, w - 1);                              // 2. reverse the whole cleaned string
    int start = 0;                                     // 3. reverse each word back to normal
    for (int i = 0; i <= w; i++) {
        if (i == w || a[i] == ' ') {
            reverse(a, start, i - 1);
            start = i + 1;
        }
    }
    return new String(a, 0, w);
}

private static void reverse(char[] a, int i, int j) {
    while (i < j) {
        char tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        i++;
        j--;
    }
}

Dry run on s = " hello world ":

step array content (first w chars) w
after squeeze hello world 11
after reversing all dlrow olleh 11
after reversing dlrow world olleh 11
after reversing olleh world hello 11

Complexity. Time O(n): three linear passes. Space O(n) for the char[] copy, O(1) beyond it.

Edge cases and pitfalls