Problem Statement

Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters.
The returned string should have exactly one space separating the words, and no leading or trailing spaces.

Example 1:
Input:

s = "the sky is blue"

Output:

"blue is sky the"

Example 2:
Input:

s = "  hello world  "

Output:

"world hello"

Example 3:
Input:

s = "a good   example"

Output:

"example good a"

---

Approach 1: Split and Reverse

This is the most straightforward solution using built-in methods.

Steps

1. Trim leading and trailing spaces from the string.
2. Split the string by spaces using regex "\\s+" which handles multiple spaces.
3. Reverse the array of words.
4. Join them back with a single space.

Time Complexity

• Splitting and joining take O(n) time.
• Overall complexity: O(n).

Space Complexity

• We store words in an array: O(n).

---

Code (Java)

public class Solution {
    public String reverseWords(String s) {
        // Trim leading/trailing spaces and split by one or more spaces
        String[] words = s.trim().split("\\s+");
        
        // Reverse the words
        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();
    }
}

---

Approach 2: Manual Reversal using Two Pointers

If we’re asked not to use split(), we can manually parse the string.

Steps

1. Trim the string.
2. Iterate backward through the string.
3. Identify each word and append it to the result.
4. Skip spaces between words.

Time Complexity

O(n) – each character is processed once.

Space Complexity

O(n) for the result string.

---

Code (Manual Parsing)

public class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        StringBuilder result = new StringBuilder();
        int end = s.length() - 1, start;

        while (end >= 0) {
            // Find start of the current word
            while (end >= 0 && s.charAt(end) == ' ') end--;
            if (end < 0) break;
            start = end;
            while (start >= 0 && s.charAt(start) != ' ') start--;
            
            // Append the word
            result.append(s.substring(start + 1, end + 1)).append(" ");
            end = start;
        }

        // Remove the last extra space
        return result.toString().trim();
    }
}

---

Dry Run

Input

s = "  hello world  "

Step-by-Step Execution

1. After trim(): "hello world"
2. Initialize end = 10, result = ""
3. end moves backward skipping trailing spaces → stays at 'd' (index 10)
4. Find start of the word: 'w' (index 6)
   → substring "world"
   → result = "world "
5. Move end = 5 (space before “world”)
6. Skip spaces → end = 4
7. Find start of the next word → 'h' (index 0)
   → substring "hello"
   → result = "world hello "
8. End of loop. Trim final result → "world hello"

Output

"world hello"

---

Key Insights

• Use split("\\s+") to handle multiple spaces efficiently.
• trim() is crucial to remove extra spaces at the ends.
• The two-pointer approach avoids split() but achieves the same result with manual control.