Reverse Words in a String

Practice Link

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.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Implementation#

Stack Approach#

Scan the string left to right, accumulating non-space characters into a temp buffer. When a space is encountered (and the buffer is non-empty), push the completed word onto the stack. After the scan, pop words off the stack one by one to build the reversed result. The stack's LIFO property naturally reverses the word order; extra spaces and consecutive spaces are handled by only pushing when temp != "".

class Solution {
public:
    string reverseWords(string s) {
        stack<string> stk;

        string temp="";
        for(char c: s)
        {
            if(c==' ' && temp!=""){
                stk.push(temp);
                temp="";
            }
            else if(c!=' '){
                temp += c;
            }
        }
        if(temp!="")
            stk.push(temp);

        string ans="";
        while(!stk.empty()){
            ans += stk.top() + " ";
            stk.pop();
        }
        ans.pop_back();
        return ans;
    }
};

Time Complexity: O(n)

Space Complexity: O(w), w -> number of words

Two Pointer — In-Place Reversal (True O(1) Space)#

The key insight: if you reverse the whole string, then reverse each word, the words end up in the right order. Three linear passes, no auxiliary storage.

1. Compact spaces — write pointer w and read pointer r copy characters into the string itself, emitting exactly one space between words and no leading/trailing spaces.
2. Reverse the entire string — a two-pointer swap from both ends.
3. Reverse each word — a two-pointer swap within each word's boundary to restore correct letter order.

"  the sky is blue  "
→ compact  → "the sky is blue"
→ rev all  → "eulb si yks eht"
→ rev words → "blue is sky the"  ✓

class Solution {
    void rev(string& s, int i, int j) {
        while (i < j) swap(s[i++], s[j--]);
    }
public:
    string reverseWords(string s) {
        int n = s.length();
        // Step 1 — compact spaces in-place
        int w = 0;
        for(int r = 0; r<n;r++){
            if(s[r] != ' '){
                if(w > 0)
                    s[w++] = ' ';
                while(r < n && s[r] != ' ')
                    s[w++] = s[r++];
            }
        }
        s.resize(w);                               // trim to actual length

        // Step 2 — reverse entire string
        reverse(s.begin(), s.end());

        // Step 3 — reverse each word back
        int start = 0;
        for(int i=0;i<=w;i++){
            if(i==w || s[i] == ' ')
            {
                reverse(s.begin()+start, s.begin() +i);
                start = i+1;
            }
        }
        return s;
    }
};

Time Complexity: O(n) — three linear passes over the string

Space Complexity: O(1) — truly in-place; no stack, no temp string

Why not prepend? Prepending ans = word + " " + ans inside a loop copies the entire result string each iteration — O(n) per word — making the total time O(n²). In-place reversal avoids this entirely.