[/dsa/leetcode]

151 - Reverse Words in a String

Wednesday, 16 September 2026

<medium> [problem]

Split on whitespace and join backwards, then the in-place version that reverses the whole string and reverses each word back in O(1) space.

{string}{two pointers}

Problem

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.

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

Input: s = "  hello world  "
Output: "world hello"

Input: s = "a good   example"
Output: "example good a"

Constraints:

  • 1 <= s.length <= 10^4
  • s contains English letters (upper-case and lower-case), digits, and spaces ' '
  • There is at least one word in s

Follow-up: if the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Approach

Split and Join

>> on a stream skips whitespace, so it does the normalising for free. See the string streams note for the details.

Collect the words, then walk the vector backwards while joining. Writing the separator before every word except the first is what keeps the output free of a trailing space, and using ans.empty() to check if its the first word as first word doesnt needs a space prefix as other would do.

class Solution {
public:
    string reverseWords(string s) {
        istringstream is(s);
        vector<string> words;
        string w;
        while (is >> w) words.push_back(w);

        string ans;
        ans.reserve(s.size());
        for (int i = words.size() - 1; i >= 0; i--) {
            if (!ans.empty()) ans += ' ';
            ans += words[i];
        }
        return ans;
    }
};
  • time: O(n) — one pass to tokenise, one to join
  • space: O(n) — the stream copies s, and every word is its own allocation

In Place Reversal

The trick is a double reversal. Reverse the entire string first: the words are now in the right order, but each one is spelled backwards. Reverse each word individually and both problems cancel out.

"a good   example"
reverse all      ->  "elpmaxe   doog a"
reverse each word->  "example   good a"

Keep idx as the next position to write to; it trails the read cursor i, so the compacted output overwrites the original from the left and never catches up to what hasn’t been read.

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        int n = s.size(), idx = 0;
        bool first = true;
        for (int i = 0; i < n; i++) {
            if (s[i] == ' ') continue;
            if (!first) s[idx++] = ' ';
            first = false;

            int j = i;
            while (j < n && s[j] != ' ') s[idx++] = s[j++];
            reverse(s.begin() + idx - (j - i), s.begin() + idx);
            i = j;
        }
        s.erase(idx);
        return s;
    }
};

j scans the word in the reversed string while idx writes it out, then the reverse flips just the j - i characters that were written. s.erase(idx) chops off whatever is left of the original.

s = "  a  b  "  ->  reversed "  b  a  "
i=2  'b'  first, no space.  write 'b'   ->  idx=1, "b"
i=5  'a'  write ' '         ->  idx=2
          write 'a'         ->  idx=3, "b a"
erase(3)  ->  "b a"
  • time: O(n) — the full reversal plus one pass, and each character is reversed once more inside its word
  • space: O(1) — everything happens inside the parameter
quantinium © 2026