1. Problem Statement

The Reverse Words in a String problem asks you to take an input string s and reverse the order of its words.

A word is defined as a sequence of non-space characters. The input string may contain leading or trailing spaces, or multiple spaces between two words. The returned string must:

• Have the words in reverse order.
• Be separated by exactly one space.
• Contain no leading or trailing spaces.

2. Examples

Example 1

Input: s = "the sky is blue" Output: "blue is sky the"

Example 2

Input: s = " hello world " Output: "world hello" Explanation: The reversed string should not contain leading or trailing spaces.

Example 3

Input: s = "a good example" Output: "example good a" Explanation: Multiple spaces between "good" and "example" are reduced to a single space in the reversed string.

3. Brute Force Approach

Intuition

The simplest way to solve this is to extract all the words from the string, put them into a list, reverse the list, and then join them back together into a single string separated by spaces.

Data Structures Used

• std::stringstream: To automatically tokenize the string and handle multiple spaces.
• std::vector<std::string>: To store the extracted words.

Algorithm

1. Create a stringstream from the input string s.
2. Extract words one by one using the >> operator, which automatically skips multiple spaces.
3. Push each word into a vector.
4. Reverse the vector.
5. Iterate through the reversed vector and append each word to a result string, adding a space between them.
6. Return the result (make sure to trim the final trailing space).

Step-by-step Dry Run

Input: " hello world "

• Stream Extraction:
  • Extract 1: "hello" -> Push to vector.
  • Extract 2: "world" -> Push to vector.
• Vector state: ["hello", "world"]
• Reverse vector: ["world", "hello"]
• Join: Result string becomes "world ", then "world hello ". Trim last space -> "world hello".

#include <string>
#include <vector>
#include <sstream>
using namespace std;  // lets us avoid writing std:: everywhere

class SolutionBrute {
public:
    string reverseWords(string s) {
        // stringstream: a helper that treats a string like input (like cin),
        // so we can extract words one by one easily, and it automatically skips extra spaces.
        stringstream ss(s);   
        string word;
        vector<string> words; // stores all extracted words
        
        // Read words from the stringstream
        while (ss >> word) {
            words.push_back(word);
        }
        
        string result = "";
        // Traverse backwards to build the reversed sentence
        for (int i = words.size() - 1; i >= 0; i--) {
            result += words[i];       // add current word
            if (i != 0) result += " "; // add space except after last word
        }
        
        return result;  // final reversed string
    }
};

Time Complexity

• $O(N)$ where $N$ is the length of the string. Iterating through the string to extract words takes linear time. Reversing and joining also takes linear time.

Space Complexity

• $O(N)$ extra space to store the parsed words in the vector.

Why this approach is inefficient

While clean and fast enough for most practical applications, it uses $O(N)$ extra memory. In an interview, the interviewer will ask: "Can you optimize the space complexity?" (Especially since C++ strings are mutable, unlike Java or Python strings).

4. Better Approach

Intuition

Instead of using a vector and reversing it, we can use a Stack. A stack follows the LIFO (Last-In-First-Out) principle, which is exactly what we need to reverse the order of elements. We read the string word by word, push each word onto the stack, and then pop them off to build the final string.

Data Structures Used

• std::stack<std::string>: To naturally reverse the order of the words.

Algorithm

1. Traverse the string, collecting characters into a temporary word variable.
2. When a space is encountered (and word is not empty), push word to the stack and clear the word variable.
3. Push the last remaining word to the stack.
4. Pop words from the stack one by one, appending them to a result string separated by a space.
5. Pop the last trailing space.

Detailed Dry Run

Input: "a good example"

• Traverse: find "a", hit space -> Stack: ["a"]
• Traverse: find "good", hit spaces -> Stack: ["a", "good"]
• Traverse: find "example", end -> Stack: ["a", "good", "example"]
• Pop 1: "example" -> Result: "example "
• Pop 2: "good" -> Result: "example good "
• Pop 3: "a" -> Result: "example good a "
• Trim last space -> "example good a"

C++ Implementation

#include <string>
#include <stack>
using namespace std;  // lets us avoid writing std:: everywhere

class SolutionBetter {
public:
    string reverseWords(string s) {
        stack<string> st;     // stack: stores words in LIFO order (last in, first out)
        string word = "";
        
        // Traverse each character in the string
        for (char c : s) {
            if (c == ' ') {
                // If we hit a space and have a word, push it onto the stack
                if (!word.empty()) {
                    st.push(word);
                    word = ""; // reset for next word
                }
            } else {
                word += c; // build the current word character by character
            }
        }
        
        // Push the last word if it exists (since loop ends without space)
        if (!word.empty()) st.push(word);
        
        string result = "";
        // Pop words from the stack (this reverses their order automatically)
        while (!st.empty()) {
            result += st.top();  // take the word on top
            st.pop();            // remove it from stack
            if (!st.empty()) result += " "; // add space if more words remain
        }
        
        return result;  // final reversed string
    }
};

Time Complexity

• $O(N)$ as we iterate through the string once to build the stack, and once to empty it.

Space Complexity

• $O(N)$ to hold the strings inside the stack.

Advantages over brute force

It removes the need to use std::reverse. The LIFO property handles the reversal organically.

Remaining bottlenecks

We are still allocating $O(N)$ extra memory for the stack and new string. In C++, strings are essentially arrays of characters that can be modified in-place.

5. Optimal Approach

The Optimal approach solves this in $O(1)$ auxiliary space using Two Pointers and In-place Reversal.

Core Intuition

If you reverse the entire string, the words will end up in the correct reversed order, but each individual word will be spelled backward. To fix this, you simply traverse the newly reversed string and reverse each individual word back to normal.

Finally, we can use two pointers to compact the string, shifting characters left to overwrite any duplicate or leading spaces, just like the "Remove Element" array problem.

Example: "the sky"

1. Reverse whole string: "yks eht"
2. Reverse each word: "sky the"

Why Two Pointers are used

Since there might be multiple spaces, we need a read pointer (i) to scan the original text and a write pointer (right) to place the valid characters at the front of the string.

Explain every data structure before coding

• std::string s: Passed by value from LeetCode (so we modify the copy), but we operate entirely within this allocated memory block. No external arrays or stacks.
• left, right: Integers acting as pointers to mark the boundaries of a word.
• i: Integer pointer to traverse the string and skip spaces.

6. Algorithm

1. Reverse the entire string using std::reverse(s.begin(), s.end()).
2. Initialize pointers: left = 0, right = 0, and i = 0.
3. Loop i through the string to find words:
   • Skip Spaces: While s[i] == ' ', increment i.
   • Add Word Spacing: If right > 0 (meaning this is not the first word), add a single space s[right] = ' ' and increment right.
   • Mark Word Start: Set left = right.
   • Copy Word: While i < length and s[i] != ' ', copy characters using s[right++] = s[i++].
   • Reverse Individual Word: Reverse the characters between left and right.
4. Resize: Since we shifted words to the front and removed extra spaces, the valid string ends at index right. Call s.resize(right) to chop off the garbage characters at the end.

7. Complete C++ Code

#include <string>
#include <algorithm>
using namespace std;  // avoids writing std:: everywhere

class Solution {
public:
    string reverseWords(string s) {
        // Step 1: Reverse the entire string
        // This flips the whole sentence so words are in reverse order,
        // but each word itself is also reversed.
        reverse(s.begin(), s.end());
        
        int n = s.size();
        int left = 0, right = 0; // pointers to mark word boundaries
        int i = 0;               // pointer to traverse the string
        
        while (i < n) {
            // Skip spaces (handles multiple spaces between words)
            while (i < n && s[i] == ' ') i++;
            if (i == n) break; // end of string reached
            
            // If not the first word, insert a single space before it
            if (right > 0) s[right++] = ' ';
            
            left = right; // mark start of current word
            
            // Copy characters of the word to the correct position
            while (i < n && s[i] != ' ') {
                s[right++] = s[i++];
            }
            
            // Step 2: Reverse the current word back to normal
            // Because the whole string was reversed earlier,
            // each word is backwards — this fixes it.
            reverse(s.begin() + left, s.begin() + right);
        }
        
        // Step 3: Resize to remove leftover characters
        s.resize(right);
        
        return s; // final reversed sentence
    }
};

8. Dry Run

Input: s = " a good "

Step 1: Reverse Entire String

s = " doog a "

Step 2: Traverse, Shift, and Reverse Words

Initialize left=0, right=0, i=0.

Step 3: Resize

right is 6. s.resize(6) chops off indices 6 onwards. Final Output: "good a"

9. Complexity Analysis

Why it is $O(1)$ Space: We do not allocate any new strings, arrays, or stacks. We only use three integer variables (i, left, right) and manipulate the existing memory array s in place

Visualisation

11. Interview Tips

• C++ specific advantage: If an interviewer asks you this question, mention immediately: "Since strings are mutable in C++, we can solve this in $O(1)$ extra space. In Java or Python, strings are immutable, so an $O(N)$ array allocation is mandatory." Interviewers love this language-specific insight.
• Common mistakes: Forgetting to place exactly one space between words during the two-pointer compaction, or forgetting to resize() the string at the end resulting in garbage characters.
• Why split the reversal? Trying to reverse words while also shifting them left simultaneously is prone to off-by-one errors. Doing a global reverse first makes the logic linear and much easier to code without bugs under interview pressure.

code link:

https://leetcode.com/problems/reverse-words-in-a-string/description/

video reference: