Reverse words in a string

Problem Link

151. Reverse Words in a String – LeetCode

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 words in s will be separated by at least one space. You must:

• Remove leading and trailing spaces.

• Reduce multiple spaces between words to a single space.

• Return the resulting string with words in reverse order.

Examples

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"

Constraints

• 1 <= s.length <= 10⁴

• s contains English letters (upper-case and lower-case), digits, and spaces ' '.

• Words are separated by at least one space.

Intuition

We need to split the string into words, ignore extra spaces, and then rebuild the sentence in reverse order.

The easiest way to reverse word order is by pushing each word into a stack, and then popping them out to build the reversed string.

Approach: Stack-Based Reversal

1. Trim leading/trailing whitespace from the string.

2. Iterate through the string character by character:

   • If you encounter a space, push the current word into a stack.

   • Otherwise, keep building the current word.

3. After the loop, push any remaining word to the stack.

4. Pop words from the stack and concatenate them with a single space.

Note: The provided code uses '_' as the space character instead of the actual space ' '. It should be corrected if tested on LeetCode.

Java Code (Corrected to Use Spaces)

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        StringBuilder sb = new StringBuilder();
        Stack<String> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ') {
                if (sb.length() > 0) {
                    stack.push(sb.toString());
                    sb.setLength(0);
                }
            } else {
                sb.append(ch);
            }
        }

        if (sb.length() > 0) stack.push(sb.toString());

        sb.setLength(0);
        if (stack.isEmpty()) return "";

        while (stack.size() > 1) {
            sb.append(stack.pop()).append(" ");
        }
        sb.append(stack.pop());

        return sb.toString();
    }
}

Time and Space Complexity

Dry Run

Input:

s = "  hello   world  "

Steps:

• Trimmed → "hello world"

• Stack pushed: "hello", "world"

• Rebuilt in reverse order: "world hello"

Output:

"world hello"

Follow-Up: Using Split and Join (Cleaner & More Efficient)

LeetCode allows usage of high-level methods:

class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
}

This approach is concise, avoids manual stack handling, and is highly readable.

Conclusion

This problem reinforces key string manipulation techniques:

• Trimming

• Splitting words

• Reversing sequences

• Managing whitespace