Reverse Words in a String

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: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = “a good example” Output: “example good a” Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

• 1 <= s.length <= 104
• 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 in your language, can you solve it in-place with O(1) extra space?

Approach: Split and Reverse (Simple Solution)

Algorithm

1. Trim leading and trailing spaces
2. Split the string by whitespace into words
3. Iterate from the last word to the first, building the result
4. Join the words with a single space

Key Insight

The problem reduces to splitting the string into words, then reversing their order. Java’s split() with a regex that matches one or more spaces handles all the extra whitespace cleanup automatically.

Time & Space Complexity

• Time Complexity: O(n) - linear in the length of the string
• Space Complexity: O(n) - stores the words and the result

Java Implementation

public class ReverseWordsInAString {

    /**
     * Reverse the order of words in a string.
     * @param s Input string
     * @return String with words in reverse order, joined by single spaces
     */
    public static String reverseWords(String s) {
        // Split on one or more whitespace characters
        String[] words = s.trim().split("\\s+");
        StringBuilder result = new StringBuilder();

        // Build the result in reverse order
        for (int i = words.length - 1; i >= 0; i--) {
            result.append(words[i]);
            if (i > 0) {
                result.append(" ");
            }
        }

        return result.toString();
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        System.out.println("Input: s = \"the sky is blue\"");
        System.out.println("Output: \"" + reverseWords("the sky is blue") + "\""); // Expected: "blue is sky the"

        // Test case 2
        System.out.println("Input: s = \"  hello world  \"");
        System.out.println("Output: \"" + reverseWords("  hello world  ") + "\""); // Expected: "world hello"

        // Test case 3
        System.out.println("Input: s = \"a good   example\"");
        System.out.println("Output: \"" + reverseWords("a good   example") + "\""); // Expected: "example good a"
    }
}

Example Walkthrough

For s = " hello world ":

1. s.trim() removes leading/trailing spaces → "hello world"
2. split("\\s+") splits into words → ["hello", "world"]
3. Iterate in reverse: append "world", then " ", then "hello"
4. Result: "world hello"

For s = "a good example":

1. s.trim() → "a good example" (no leading/trailing spaces)
2. split("\\s+") collapses multiple spaces → ["a", "good", "example"]
3. Reverse order: "example", " ", "good", " ", "a"
4. Result: "example good a"

Alternative Approach: Two-Pointer Word Extraction

public static String reverseWordsTwoPointer(String s) {
    StringBuilder result = new StringBuilder();
    int i = s.length() - 1;

    while (i >= 0) {
        // Skip trailing spaces
        while (i >= 0 && s.charAt(i) == ' ') {
            i--;
        }

        if (i < 0) {
            break;
        }

        // Find the end of the word
        int end = i;
        while (i >= 0 && s.charAt(i) != ' ') {
            i--;
        }

        // Extract and append the word
        if (result.length() > 0) {
            result.append(' ');
        }
        result.append(s, i + 1, end + 1);
    }

    return result.toString();
}

This approach scans from the end and extracts words one at a time, still using O(n) extra space for the result but avoiding the intermediate split array.

Key Insights

1. Whitespace Handling: split("\\s+") handles leading, trailing, and multiple spaces cleanly
2. Reverse Iteration: Iterating the split array backwards naturally reverses word order
3. Single Space Join: The result is joined with exactly one space between words
4. Follow-up: The two-pointer approach shows a pattern that can be adapted for in-place reversal with O(1) extra space in mutable languages

The split-and-reverse approach is the simplest and most readable solution for this problem.