Reverse Words in a String

Problem: Given a string str of length N, reverse the string word by word (the order of the words is reversed, but each individual word is not reversed).

Constraints: The input can contain multiple consecutive spaces between words and leading/trailing spaces. The output must contain exactly a single space between words and no leading/trailing spaces.

Example: Input: " the sky is blue " -> Output: "blue is sky the".

Approach: Split the string on whitespace (collapsing multiple spaces and dropping leading/trailing empty tokens), reverse the resulting list of words, then join with a single space. O(n) time, O(n) space. An in-place O(1)-extra-space variant: reverse the entire string, then reverse each word in place, then clean up extra spaces.