Author at SyntaxFlow
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:
Input: s = "the sky is blue" Output: "blue is sky the"
Input: s = " hello world " Output: "world hello" Explanation: The reversed string should not contain leading or trailing spaces.
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.
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.
std::stringstream: To automatically tokenize the string and handle multiple spaces.std::vector<std::string>: To store the extracted words.stringstream from the input string s.>> operator, which automatically skips multiple spaces.vector.vector.result string, adding a space between them.result (make sure to trim the final trailing space).Input: " hello world "
"hello" -> Push to vector."world" -> Push to vector.["hello", "world"]["world", "hello"]"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
}
};
While clean and fast enough for most practical applications, it uses 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).
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.
std::stack<std::string>: To naturally reverse the order of the words.word variable.word is not empty), push word to the stack and clear the word variable.result string separated by a space.Input: "a good example"
"a", hit space -> Stack: ["a"]"good", hit spaces -> Stack: ["a", "good"]"example", end -> Stack: ["a", "good", "example"]"example" -> Result: "example ""good" -> Result: "example good ""a" -> Result: "example good a ""example good a"#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
}
};
It removes the need to use std::reverse. The LIFO property handles the reversal organically.
We are still allocating extra memory for the stack and new string. In C++, strings are essentially arrays of characters that can be modified in-place.
The Optimal approach solves this in auxiliary space using Two Pointers and In-place Reversal.
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"
"yks eht""sky the"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.
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.std::reverse(s.begin(), s.end()).left = 0, right = 0, and i = 0.i through the string to find words:s[i] == ' ', increment i.right > 0 (meaning this is not the first word), add a single space s[right] = ' ' and increment right.left = right.i < length and s[i] != ' ', copy characters using s[right++] = s[i++].left and right.right. Call s.resize(right) to chop off the garbage characters at the end.#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
}
};
Input: s = " a good "
s = " doog a "
Initialize left=0, right=0, i=0.
right is 6. s.resize(6) chops off indices 6 onwards. Final Output: "good a"
Why it is 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
resize() the string at the end resulting in garbage characters.code link:
https://leetcode.com/problems/reverse-words-in-a-string/description/
video reference: