151. Reverse Words in a String

Given a string s, reverse the order of the words (not characters). Words are separated by spaces; input may contain leading/trailing/multiple spaces which must be collapsed into single spaces in the output.

Input " the sky is blue " → output "blue is sky the".

1. trim() the input to remove leading/trailing whitespace.
2. Use two pointers (first, second) to scan and extract each word: skip spaces by advancing first; advance second from first until a space or end of string is hit; extract the word via s.substring(first, second).
3. Store words in a List<String> (size unknown up front → can't use a fixed-size array).
4. Collections.reverse(words) to reverse word order (not characters).
5. String.join(" ", words) to rebuild the final string.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        List<String> words = new ArrayList<>();
        int first = 0;

        while (first < s.length()) {
            if (s.charAt(first) == ' ') {
                first++;
                continue;
            }
            int second = first;
            while (second < s.length() && s.charAt(second) != ' ') {
                second++;
            }
            words.add(s.substring(first, second));
            first = second;
        }

        Collections.reverse(words);
        return String.join(" ", words);
    }
}

OCA concepts reinforced (chapter 3)

• String immutability — why looping += on Strings is wasteful; StringBuilder/List + String.join() avoid the string pool churn.
• substring(begin, end) — end index is exclusive. Classic exam trap.
• Array vs. ArrayList — arrays need a fixed size declared up front; use ArrayList/List when the size is unknown (word count here).
• Generics / diamond operator — List<String> words = new ArrayList<>(); avoids raw-type warnings and unchecked-conversion issues.
• Collections.reverse() — a java.util.Collections helper, same family as Collections.sort().

Java 8

Fine — String.join() (Java 8), diamond operator (Java 7+).

• Time: O(n) — each character visited a constant number of times.
• Space: O(n) — for the word list and rebuilt string.

• Can I write it from memory without looking?
• Can I do it in place on a char[] (reverse the whole string, then each word) with O(1) extra space?