SyntaxPilot
Courses/C++ Coding Questions/Lesson 7
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 7 of 30

String questions III

reverse the words of a sentence (stringstream)remove duplicate characters keeping orderrun-length compression (aaabb → a3b2); s + c in a loop

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 >> w reads 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() - 1 would 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.

  1. A run is written only when the next letter differs. The last run has no next letter, so it is never written (b2, c1, b1 are missing).
  2. 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

  1. Reverse the words of a sentence. Split with stringstream and walk back (O(n) space), or reverse the whole string and then each word (O(1) extra space).
  2. Why does std::reverse on the line not work? It reverses characters, so each word comes out backwards.
  3. Remove duplicate characters keeping the order. A seen[256] array (or unordered_set<char>): keep a character the first time.
  4. Why is sort + unique wrong here? It loses the original order.
  5. Run-length encode a string. What edge cases? The last run, counts ≥ 10, a single character, an empty string.
  6. Why is s = s + c in a loop slow? It builds a new string and copies everything each time: O(n²). s += c is amortised O(1).
  7. 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.
  8. How do you turn a number into a string? to_string(n); and back with stoi(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 stringstream into a vector<string>, walk it backwards, one space between words. std::reverse on 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, never char('0' + count).
  • In a loop, always out += x: out = out + x copies 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.