Reverse Words in a String — Editorial

Opening the reading…

Intuitionwhy two reversals produce the required word order

Reversing the complete string puts the words in reverse order, but also reverses every word internally. For example, the characters in the first word become the characters of the last word, but in backward order. Reversing each word after the whole-string reversal restores its letters while keeping its new position, so the two reversals cancel at the character level and remain effective at the word level.

The spaces need separate treatment because the result must contain exactly one space between words. While scanning from left to right, skip every space before a word, copy the word to the next compact position, reverse that copied range, and append one separator. The read pointer explores the original content, while the write pointer builds the cleaned result inside the same string.

The read pointer consumes the input while the write pointer creates the cleaned prefix.

Approachone scan, one compaction, and one local reversal

Reverse the entire string first, because this moves the words into their final left-to-right order while reversing the letters inside each word.

Set i as the read position and set left and right to describe the next word's destination range, because the write position must not be confused with the amount of original input already inspected.

Skip spaces with i before every word, because leading spaces and repeated separators must not be copied into the result.

Copy the next maximal non-space sequence from i to right, because compacting into the front of s removes gaps without allocating another working string.

Reverse the copied range from left through right - 1, because the whole-string reversal left this word's characters backward.

Write one space after the recovered word and move left to the next output position, because every word needs exactly one separator while the final separator can be removed afterward.

Resize s to right - 1 and return it, because the loop deliberately appends a temporary space after the last word and that space is not part of the answer.

Complexitythe input buffer is reused as working memory

MEASURE	BOUND	WHY
Time	O(n)	The whole string is reversed once, each character is read at most once during compaction, and each copied word is reversed once. The word ranges are disjoint, so the total number of character operations across all local reversals is at most n.
Space	O(1) extra	The output remains inside the mutable input string, so output storage is excluded. The algorithm uses only indices and the in-place reverse operation; its extra working space stays constant, including when the input has the worst shape of many short words or many spaces.

Here n is the length of the input string s.

Annotated solutionC++ · in-place two-pointer compaction

CPPReverse the whole string, compact each word, reverse that word, and remove the final temporary space.

#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());

        int n = static_cast<int>(s.size());
        int i = 0;
        int left = 0;
        int right = 0;

        while (i < n) {
            while (i < n && s[i] == ' ') {
                ++i;
            }

            if (i == n) {
                break;
            }

            while (i < n && s[i] != ' ') {
                s[right++] = s[i++];
            }

            reverse(s.begin() + left, s.begin() + right);
            s[right++] = ' ';
            left = right;
        }

        s.resize(right - 1);
        return s;
    }
};

The key invariant is that the prefix before right already contains the answer's recovered words, separated by single spaces, while i has consumed the corresponding portion of the reversed input. The assignment s[right++] = s[i++] is safe because right never moves ahead of i during compaction. Once a word is copied, left and right isolate exactly that word, so its local reverse cannot disturb earlier output.

The extra-space alternativesimpler construction at the cost of linear working memory

A competent alternative scans from the end, skips spaces, identifies each word, and appends it directly to a new result string. It avoids the temporary reversed characters and is often easier to explain, but it uses O(n) extra space for the result and does not satisfy the in-place goal suggested by the two-pointer method. It is a different arrangement, not an optimisation.

CPPScan words from right to left and append them to a separately allocated result string.

#include <string>

using namespace std;

class Solution {
public:
    string reverseWords(string s) {
        string result;
        int i = static_cast<int>(s.size()) - 1;

        while (i >= 0) {
            while (i >= 0 && s[i] == ' ') {
                --i;
            }

            if (i < 0) {
                break;
            }

            int end = i;
            while (i >= 0 && s[i] != ' ') {
                --i;
            }

            if (!result.empty()) {
                result.push_back(' ');
            }
            result.append(s, i + 1, end - i);
        }

        return result;
    }
};