1. Understanding the Problem

You are given an input string s. Your task is to 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.

The Core Constraints & Edge Cases:

• s may contain leading or trailing spaces (e.g., " hello world ").
• s may contain multiple spaces between two words (e.g., "a good example").
• The returned string must have only a single space separating words and no extra spaces at the beginning or end.
• Follow-up challenge: If strings are mutable in your language (like C++), can you solve it in-place with O(1) extra space?

2. The Naive Approach: Split, Reverse, and Join

In high-level languages like Python or Java, the most straightforward approach is to split the string by whitespace, reverse the resulting list of words, and join them back together with a single space.

Trade-off Analysis

• Time Complexity: O(N) — Splitting, reversing, and joining all scale linearly with string length N.
• Space Complexity: O(N) — Storing the parsed words requires extra memory proportional to the size of the string.
• While perfectly acceptable in languages with immutable strings (like Java and Python), interviewers in C/C++ often expect you to demonstrate an in-place two-pointer technique.

3. The Optimal Approach: Two-Pass Reverse & Cleanup (In-Place for C++)

To achieve O(1) extra space in languages with mutable strings (C++):

1. Reverse the Entire String: Reversing the entire string puts words in their correct relative positions, but each individual word is flipped backward.
2. Reverse Each Word: Iterate through the string using two pointers to identify word boundaries, then reverse each word to make it readable again.
3. Clean Up Spaces: Shift valid characters forward to eliminate leading, trailing, and duplicate spaces, then truncate the string.

In languages with immutable strings (Python, Java), we simulate this cleanly by scanning backward or parsing tokens directly into a builder to keep memory efficient.

4. The Logic Step-by-Step

1. Scan Backward (or Parse Tokens): Start scanning the string from the end toward the beginning.
2. Identify Words:
   • Skip over any whitespace characters.
   • When a non-space character is found, mark the end index of the word.
   • Move backward until a space is hit (or the beginning of the string) to find the start index of the word.
3. Build Output: Extract the word between start + 1 and end, append it to the result, and insert a single space between adjacent words.
4. Return the cleaned, reversed string.

5. Complexity Analysis

• Time Complexity: O(N) — We perform a constant number of passes over the string of length N.
• Space Complexity: O(N) in Python/Java due to string immutability (storing output). O(1) extra space in C++ by modifying the string in-place.

6. Code Implementations

Expand the sections below to see idiomatic implementations across different languages.

class Solution:
    def reverseWords(self, s: str) -> str:
        # split() without arguments automatically handles arbitrary whitespace,
        # strips leading/trailing spaces, and ignores multiple spaces between words.
        words = s.split()
        
        # Reverse the list of words and join them with a single space
        return " ".join(words[::-1])

class Solution {
    public String reverseWords(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;

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

            // Append space if result already has words
            if (result.length() > 0) {
                result.append(" ");
            }

            // Append extracted word
            result.append(s.substring(i + 1, j + 1));
        }

        return result.toString();
    }
}

#include <string>
#include <algorithm>

class Solution {
public:
    std::string reverseWords(std::string s) {
        // Step 1: Reverse the whole string
        std::reverse(s.begin(), s.end());

        int n = s.length();
        int idx = 0; // Pointer for building cleaned string

        for (int start = 0; start < n; ++start) {
            if (s[start] != ' ') {
                // Add a space before word if it's not the first word
                if (idx != 0) s[idx++] = ' ';

                int end = start;
                while (end < n && s[end] != ' ') {
                    s[idx++] = s[end++];
                }

                // Reverse the word back to correct order
                std::reverse(s.begin() + idx - (end - start), s.begin() + idx);

                start = end;
            }
        }

        // Truncate string to remove leftover old characters
        s.resize(idx);
        return s;
    }
};

7. Conclusion: You Are Ready

Congratulations! You have mastered reversing words in a string with full whitespace handling. Whether you leverage built-in split/join utilities or perform in-place character swaps and index shifts using two pointers, you now possess the core mechanics needed to handle complex string manipulation problems in technical interviews. Keep refining your pointer skills and happy coding!