These are the notes for C++ Coding Questions, episode 7, placement practice for people who finished the SyntaxPilot C++ course. Strings, part three: reversing the words of a sentence, removing duplicate characters while keeping their order, and run-length compression (aaabb → a3b2), plus the hidden O(n²) cost of s = s + c in a loop.
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program after 8 seconds (Time Limit Exceeded, TLE), like an online judge.
Real-life pictures
| In real life | In C++ |
|---|---|
| A train goes Mumbai → Pune → Bengaluru; the return board says Bengaluru → Pune → Mumbai, not "urulagneB" | reverse the order of the words, not the letters |
| A wedding register where some guests sign twice: keep a tick list, keep each name the first time | remove duplicates with a seen[] array, order kept |
| Sorting the register A to Z to drop repeats: now you can't tell who came first | sort + unique loses the order |
| A kirana bill says "milk × 3, bread × 2", not "milk milk milk bread bread"; a dozen eggs is "× 12" | run-length compression: aaabb → a3b2; counts can have 2+ digits |
| Adding one word to a page by copying the whole page onto a new sheet first | out = out + c copies the whole string every time: O(n²) |
Q1: Reverse the words of a sentence
Problem. For each line, print its words in reverse order, separated by one space.
| Input | Output |
|---|---|
I love chai |
chai love I |
hello world |
world hello |
single |
single |
| (empty line) | (empty line) |
The obvious attempt: std::reverse on the whole line
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string s;
while (getline(cin, s)) {
reverse(s.begin(), s.end());
cout << "[" << s << "]\n";
}
return 0;
}
Output:
[iahc evol I]
[ dlrow olleh ]
[elgnis]
Wrong: the word order flipped, but so did every letter, and the extra spaces are still there. std::reverse works on characters; it doesn't know what a word is.
Fix: split into words, walk them backwards
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
int main() {
string s;
while (getline(cin, s)) {
stringstream ss(s);
vector<string> words;
string w;
while (ss >> w) words.push_back(w);
string out = "";
for (int i = (int)words.size() - 1; i >= 0; i--) {
out += words[i];
if (i > 0) out += " ";
}
cout << "[" << out << "]\n";
}
return 0;
}
Output:
[chai love I]
[world hello]
[single]
Input: an empty line:
[]
stringstream ss(s)+ss >> wreads one word at a time and skips any number of spaces, so the extra spaces disappear.- The words go into a
vector<string>; the loop walks it from the back and adds a space only between words (if (i > 0)). (int)words.size() - 1:size()is unsigned; for an empty vector,size() - 1would wrap to a huge number.
Complexity: O(n) time (each character read once), O(n) extra space for the words.
Interview follow-up (O(1) extra space): reverse the whole string, then reverse each word back. See practice question 1 for the "reverse each word" half.
Q2: Remove duplicate characters, keep the order
Problem. For each word, keep every character only the first time it appears.
| Input | Output |
|---|---|
| programming | progamin |
| banana | ban |
| aabbcc | abc |
| xyz | xyz |
The obvious attempt: sort + unique (the erase-unique idiom)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string s;
while (cin >> s) {
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
cout << s << "\n";
}
return 0;
}
Input programming banana aabbcc:
agimnopr
abn
abc
Every letter appears once, but in alphabetical order: sort destroyed the original order (banana should give ban, not abn). (unique removes only adjacent repeats, which is why it needs the sort, and erase cuts off the leftovers: more on this idiom in episode 9.)
Fix: a seen[256] tick list
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
while (cin >> s) {
bool seen[256] = {};
string out = "";
for (char ch : s) {
unsigned char c = ch;
if (!seen[c]) {
seen[c] = true;
out += ch;
}
}
cout << out << "\n";
}
return 0;
}
Input programming banana aabbcc xyz:
progamin
ban
abc
xyz
One tick box per possible character value. The character is converted to unsigned char before being used as an index, so a negative char can never index outside the array. O(n) time, O(1) extra space (256 bools, whatever the input size) plus the output.
Q3: Run-length compression
Problem. Write each run of the same letter as the letter followed by the run's length.
| Input | Output |
|---|---|
| aaabb | a3b2 |
| abc | a1b1c1 |
| aaaaaaaaaaaab (12 a's) | a12b1 |
| a | a1 |
The obvious attempt: compare each letter with the next
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
while (cin >> s) {
string out = "";
int count = 1;
for (int i = 0; i + 1 < (int)s.size(); i++) {
if (s[i] == s[i + 1]) count++;
else {
out += s[i];
out += char('0' + count);
count = 1;
}
}
cout << out << "\n";
}
return 0;
}
Input aaabb abc aaaaaaaaaaaab:
a3
a1b1
a<
Two bugs.
- A run is written only when the next letter differs. The last run has no next letter, so it is never written (
b2,c1,b1are missing). char('0' + count)only works for one digit.'0'is character code 48; 48 + 12 = 60, which is'<'.
Fix: scan each whole run with a second index, and to_string
#include <iostream>
#include <string>
using namespace std;
string compress(const string& s) {
string out = "";
int n = s.size();
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s[j] == s[i]) j++;
out = out + s[i] + to_string(j - i);
i = j;
}
return out;
}
int main() {
string s;
while (cin >> s) {
if (s == "big") { // test: abab... 600,000 letters
s = "";
for (int i = 0; i < 600000; i++) s += (i % 2 ? 'b' : 'a');
}
string c = compress(s);
cout << s.size() << " -> " << c.size() << ": " << c.substr(0, 20) << "\n";
}
return 0;
}
Input aaabb abc aaaaaaaaaaaab a:
5 -> 4: a3b2
3 -> 6: a1b1c1
13 -> 5: a12b1
1 -> 2: a1
For each run starting at i, j walks to its end; the length is j - i, and to_string writes all its digits. The last run is handled like any other.
But input big (the test line builds abab..., 600,000 letters): Time Limit Exceeded.
Why: out = out + s[i] + ... copies the whole string every time
out + s[i] builds a brand-new string: a full copy of out plus one character. Then = replaces out with it. When out has k characters, that step copies k characters, so building an output of length m costs about 1 + 2 + ... + m ≈ m²/2 copies. Here m = 1,200,000: hundreds of billions of character copies.
Fix: +=
#include <iostream>
#include <string>
using namespace std;
string compress(const string& s) {
string out = "";
int n = s.size();
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s[j] == s[i]) j++;
out += s[i];
out += to_string(j - i);
i = j;
}
return out;
}
int main() {
string s;
while (cin >> s) {
if (s == "big") { // test: abab... 600,000 letters
s = "";
for (int i = 0; i < 600000; i++) s += (i % 2 ? 'b' : 'a');
}
string c = compress(s);
cout << s.size() << " -> " << c.size() << ": " << c.substr(0, 20) << "\n";
}
return 0;
}
Input aaabb abc aaaaaaaaaaaab a big:
5 -> 4: a3b2
3 -> 6: a1b1c1
13 -> 5: a12b1
1 -> 2: a1
600000 -> 1200000: a1b1a1b1a1b1a1b1a1b1
out += x appends at the end of the existing string. A std::string keeps spare capacity and grows it geometrically (roughly doubling), so a long series of appends costs amortised O(1) each: O(n) in total.
Note: for abab... "compression" doubles the length; see practice question 2 for "compress only if it gets shorter".
Complexity summary
| Program | Time | Extra space |
|---|---|---|
reverse words, stringstream + vector |
O(n) | O(n) |
| remove duplicates, sort + unique | O(n log n) | O(1), but order lost |
remove duplicates, seen[256] |
O(n) | O(1) + output |
compress, out = out + ... |
O(n²) | O(n) |
compress, out += ... |
O(n) | O(n) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
reverse(s.begin(), s.end()) for words |
iahc evol I |
reverses characters | split into words, walk back |
| words joined with a space after each | trailing space | the last word also gets one | add a space only if (i > 0) |
sort + unique to remove repeats |
agimnopr |
sorting loses the order | bool seen[256] |
| write a run when the next letter differs | a3 (no b2) |
the last run is never written | scan each run with j |
char('0' + count) |
a< |
'0' + 12 is '<' |
to_string(count) |
out = out + c; in a loop |
Time Limit Exceeded | copies all of out each time |
out += c; |
Your turn: decompress (solution)
Problem. Turn a3b2 back into aaabb; counts can have several digits.
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
string decompress(const string& s) {
string out = "";
int n = s.size();
for (int i = 0; i < n; ) {
char letter = s[i++];
int count = 0;
while (i < n && isdigit((unsigned char)s[i]))
count = count * 10 + (s[i++] - '0'); // read ALL the digits
out += string(count, letter);
}
return out;
}
int main() {
string s;
while (cin >> s)
cout << s << " -> " << decompress(s) << "\n";
return 0;
}
Input a3b2 a12b1 x1 c10:
a3b2 -> aaabb
a12b1 -> aaaaaaaaaaaab
x1 -> x
c10 -> cccccccccc
count = count * 10 + digit builds a multi-digit number one digit at a time; string(count, letter) makes count copies of letter. O(output length) time.
Practice questions (with solutions)
1. Reverse each word, keep the word order (I love chai → I evol iahc, spaces kept).
Solution
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string s;
while (getline(cin, s)) {
int n = s.size();
for (int i = 0; i < n; ) {
if (s[i] == ' ') { i++; continue; }
int j = i;
while (j < n && s[j] != ' ') j++;
reverse(s.begin() + i, s.begin() + j); // reverse just this word
i = j;
}
cout << "[" << s << "]\n";
}
return 0;
}
Input I love chai / hello world:
[I evol iahc]
[ olleh dlrow ]
Reverse the whole line first and then run this, and you have reversed the words in place.
2. Compress only if it gets shorter.
Solution
#include <iostream>
#include <string>
using namespace std;
string compress(const string& s) {
string out = "";
int n = s.size();
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s[j] == s[i]) j++;
out += s[i];
out += to_string(j - i);
i = j;
}
return out.size() < s.size() ? out : s; // only if it really got shorter
}
int main() {
string s;
while (cin >> s)
cout << s << " -> " << compress(s) << "\n";
return 0;
}
Input aaabb abc aaaaaaaaaaaab aabb:
aaabb -> a3b2
abc -> abc
aaaaaaaaaaaab -> a12b1
aabb -> aabb
3. Remove all spaces from a line, in place (a write index, then resize).
Solution
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
while (getline(cin, s)) {
int write = 0;
for (char c : s)
if (c != ' ') s[write++] = c;
s.resize(write);
cout << "[" << s << "]\n";
}
return 0;
}
Input chai pe charcha:
[chaipecharcha]
Mini project: a sentence report
The reversed sentence, and the distinct letters in the order they first appear.
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
int main() {
string s;
while (getline(cin, s)) {
stringstream ss(s);
vector<string> words;
string w;
while (ss >> w) words.push_back(w);
string reversedWords = "", letters = "";
bool seen[256] = {};
for (int i = (int)words.size() - 1; i >= 0; i--) {
reversedWords += words[i];
if (i > 0) reversedWords += " ";
}
for (char ch : s) {
unsigned char c = ch;
if (ch != ' ' && !seen[c]) { seen[c] = true; letters += ch; }
}
cout << "words reversed: [" << reversedWords << "]\n";
cout << "letters used: [" << letters << "]\n";
}
return 0;
}
Input I love masala chai:
words reversed: [chai masala love I]
letters used: [Ilovemaschi]
Quick quiz
#include <iostream>
#include <string>
using namespace std;
int main() {
string out = "";
int count = 15;
out += 'x';
out += char('0' + count);
out += to_string(count);
cout << out << "\n";
return 0;
}
(A) x?15 (B) x1515 (C) x15 (D) x?
Answer
(A) x?15. '0' + 15 = 48 + 15 = 63, the character '?'. to_string(15) is "15".
x?15
Interview questions
- Reverse the words of a sentence. Split with
stringstreamand walk back (O(n) space), or reverse the whole string and then each word (O(1) extra space). - Why does
std::reverseon the line not work? It reverses characters, so each word comes out backwards. - Remove duplicate characters keeping the order. A
seen[256]array (orunordered_set<char>): keep a character the first time. - Why is
sort+uniquewrong here? It loses the original order. - Run-length encode a string. What edge cases? The last run, counts ≥ 10, a single character, an empty string.
- Why is
s = s + cin a loop slow? It builds a new string and copies everything each time: O(n²).s += cis amortised O(1). - What is amortised O(1)? Most appends are O(1); the occasional reallocation is O(n), but it happens so rarely (capacity grows geometrically) that the average per append is constant.
- How do you turn a number into a string?
to_string(n); and back withstoi(s).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Word | A run of non-space characters | chai |
stringstream |
Read a string like cin, from <sstream> |
ss >> w |
vector<string> |
A resizable list of strings | the words of a line |
| Join | Glue words back together with a separator | chai love I |
| Duplicate | A value that already appeared earlier | the second r in programming |
Tick list (seen[]) |
A bool per possible value: already seen? | bool seen[256] |
| Erase-unique idiom | s.erase(unique(b, e), e): drop adjacent repeats |
after sort |
| Run | Consecutive equal characters | aaa in aaabb |
| Run-length encoding (RLE) | Store each run as character + length | a3b2 |
to_string |
A number as a string | to_string(12) = "12" |
| Character code | The number a char is stored as (ASCII) |
'0' = 48, '<' = 60 |
| Concatenation | Joining strings with + |
out + s[i] |
| Capacity | Memory a string has reserved beyond its size | grows by doubling |
| Amortised O(1) | Constant time on average over many operations | += / push_back |
| O(n²) | Work grows with the square of n | out = out + c in a loop |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | 8 seconds here |
Summary
- Reverse the words: split with
stringstreaminto avector<string>, walk it backwards, one space between words.std::reverseon the line reverses letters. - Remove duplicates, keep order: a
bool seen[256]tick list. Sorting loses the order. - Compress: scan each whole run with a second index (the last run included), and write the count with
to_string, neverchar('0' + count). - In a loop, always
out += x:out = out + xcopies the whole string every time (O(n²)).
Next episode: Vector questions I: the largest and second largest element (duplicates and negatives), rotating a vector by k (k % n, std::rotate), and moving all zeros to the end while keeping the order.