SyntaxPilot
Courses/C++ Coding Questions/Lesson 6
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 6 of 30

String questions II

anagram check (sort vs counting array)first non-repeating characterfrequency of every character (map vs array)

These are the notes for C++ Coding Questions, episode 6, placement practice for people who finished the SyntaxPilot C++ course. Strings, part two: anagram check (sorting vs a counting array, timed for real), the first non-repeating character, and the frequency of every character with map, unordered_map and a plain array. All three are secretly the same idea: count once, then look up.

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. Timings depend on the machine; the ones below are from one run.

Real-life pictures

In real life In C++
Two grocery bags from the kirana shop with the same items packed in a different order an anagram: the same letters in any order (listen / silent)
Line up both bags' items in the same order, then compare sort both strings: O(n log n)
A tally sheet: +1 for every item in bag one, −1 for bag two; all zeros = same items a counting array int cnt[26]: O(n)
A class-monitor election counted with a tally mark per slip, one box per name a frequency table
The first person in the chai-stall queue whose order nobody else gave the first non-repeating character

The counting array: c - 'a'

Characters are stored as numbers ('a' = 97, 'b' = 98, ... 'z' = 122), so for a small letter c, c - 'a' is 0 for 'a', 1 for 'b', ..., 25 for 'z': a box number. Going back: char('a' + i).

This only works for 'a' to 'z'. For any character use int cnt[256] and index it with (unsigned char)c (a char can be negative, and a negative index is out of bounds).

Q1: Are a and b anagrams?

Problem. Read pairs of lower-case words and print whether each pair are anagrams.

Input Output
listen silent anagram
earth heart anagram
aab abb not
cat cats not
chai chat not

The obvious attempt: every letter of a appears in b

#include <iostream>
#include <string>
using namespace std;

bool isAnagram(const string& a, const string& b) {
    for (char c : a)
        if (b.find(c) == string::npos) return false;
    return true;
}

int main() {
    string a, b;
    while (cin >> a >> b)
        cout << a << " " << b << (isAnagram(a, b) ? " -> anagram\n" : " -> not\n");
    return 0;
}

Output:

listen silent -> anagram
earth heart -> anagram
aab abb -> anagram
cat cats -> anagram
chai chat -> not

Wrong for aab abb and cat cats. find only asks is this letter there?, never how many times?, and nothing checks the extra letters in b.

Fix 1: sort both

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isAnagram(string a, string b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    return a == b;
}

int main() {
    string a, b;
    while (cin >> a >> b)
        cout << a << " " << b << (isAnagram(a, b) ? " -> anagram\n" : " -> not\n");
    return 0;
}

Output:

listen silent -> anagram
earth heart -> anagram
aab abb -> not
cat cats -> not
chai chat -> not

Anagrams always sort to the same string (listen, silent → eilnst). The parameters are taken by value (copies), so the caller's strings are not changed. O(n log n) time, O(n) for the copies.

Fix 2: a counting array (the tally sheet)

#include <iostream>
#include <string>
using namespace std;

bool isAnagram(const string& a, const string& b) {
    if (a.size() != b.size()) return false;
    int cnt[26] = {};
    for (char c : a) cnt[c - 'a']++;
    for (char c : b) cnt[c - 'a']--;
    for (int i = 0; i < 26; i++)
        if (cnt[i] != 0) return false;
    return true;
}

int main() {
    string a, b;
    while (cin >> a >> b)
        cout << a << " " << b << (isAnagram(a, b) ? " -> anagram\n" : " -> not\n");
    return 0;
}

Same output, all correct. O(n) time, O(1) extra space (26 ints). The length check first is free and handles cat cats immediately.

Is counting really faster? Timed on 20 million letters

#include <iostream>
#include <string>
#include <algorithm>
#include <chrono>
using namespace std;
using namespace std::chrono;

bool bySort(string a, string b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    return a == b;
}

bool byCount(const string& a, const string& b) {
    if (a.size() != b.size()) return false;
    int cnt[26] = {};
    for (char c : a) cnt[c - 'a']++;
    for (char c : b) cnt[c - 'a']--;
    for (int i = 0; i < 26; i++)
        if (cnt[i] != 0) return false;
    return true;
}

int main() {
    string a, b;
    for (int i = 0; i < 20000000; i++) a += char('a' + i * 7 % 26);
    b = a;
    reverse(b.begin(), b.end());
    auto t0 = steady_clock::now();
    bool r1 = bySort(a, b);
    auto t1 = steady_clock::now();
    bool r2 = byCount(a, b);
    auto t2 = steady_clock::now();
    cout << "sort:  " << r1 << " in " << duration_cast<milliseconds>(t1 - t0).count() << " ms\n";
    cout << "count: " << r2 << " in " << duration_cast<milliseconds>(t2 - t1).count() << " ms\n";
    return 0;
}

Output (one run):

sort:  1 in 641 ms
count: 1 in 20 ms

Both say 1 (true); counting was about 30 times faster here. (In the video, on the SyntaxPilot compiler, the same program printed sort: 1 in 1219 ms and count: 1 in 31 ms.) steady_clock from <chrono> is a stopwatch: take the time before and after, and convert the difference with duration_cast<milliseconds>.

Q2: First non-repeating character

Problem. For each word (lower case, up to 300,000 letters), print the index and letter of the first character that appears exactly once, or none.

Input Output
swiss index 1: w
leetcode index 0: l
aabb none
x index 0: x
chai index 0: c

Edge cases: no unique letter, the answer at the very end, a huge word.

The obvious attempt: count each letter with a second loop

#include <iostream>
#include <string>
using namespace std;

int firstUnique(const string& s) {
    int n = s.size();
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++)
            if (s[j] == s[i]) count++;
        if (count == 1) return i;
    }
    return -1;
}

int main() {
    string s;
    while (cin >> s) {
        if (s == "big") s = string(300000, 'a') + "z";   // test: 300,000 letters
        int i = firstUnique(s);
        if (i == -1) cout << "none\n";
        else cout << "index " << i << ": " << s[i] << "\n";
    }
    return 0;
}

(The "big" line is only a test helper: typing big builds a word of 300,000 as followed by z, because nobody can type that much.)

Input swiss leetcode aabb x:

index 1: w
index 0: l
none
index 0: x

Input big: Time Limit Exceeded. For each of the n letters it scans all n letters: n × n = 300,000 × 300,000 = 90 billion steps.

Attempt: count once in a std::map, then loop over the map

#include <iostream>
#include <string>
#include <map>
using namespace std;

char firstUnique(const string& s) {
    map<char, int> freq;
    for (char c : s) freq[c]++;
    for (auto [c, count] : freq)
        if (count == 1) return c;
    return '-';
}

int main() {
    string s;
    while (cin >> s)
        cout << s << " -> " << firstUnique(s) << "\n";
    return 0;
}

Input swiss leetcode aabb chai:

swiss -> i
leetcode -> c
aabb -> -
chai -> a

Wrong: the answers should be w, l, c. A std::map keeps its keys sorted: for swiss it is { i:1, s:3, w:1 }, so looping over it finds the first unique letter in the alphabet, not in the word. The map forgot where each letter was.

Fix: two passes, the second over the string

#include <iostream>
#include <string>
using namespace std;

int firstUnique(const string& s) {
    int cnt[26] = {};
    for (char c : s) cnt[c - 'a']++;
    for (int i = 0; i < (int)s.size(); i++)
        if (cnt[s[i] - 'a'] == 1) return i;
    return -1;
}

int main() {
    string s;
    while (cin >> s) {
        if (s == "big") s = string(300000, 'a') + "z";   // test: 300,000 letters
        int i = firstUnique(s);
        if (i == -1) cout << "none\n";
        else cout << "index " << i << ": " << s[i] << "\n";
    }
    return 0;
}

Input swiss leetcode aabb x chai big:

index 1: w
index 0: l
none
index 0: x
index 0: c
index 300000: z

Pass one counts every letter; pass two walks the string in its own order and returns the first index whose count is 1. The huge word is instant. O(n) time, O(1) extra space.

Q3: Frequency of every character

Problem. Read a lower-case word and print every letter that appears, once, with its count (in alphabetical order).

hello → e 1, h 1, l 2, o 1.

The obvious attempt: std::count for every character

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    for (char c : s)
        cout << c << " " << count(s.begin(), s.end(), c) << "\n";
    return 0;
}

Input hello:

h 1
e 1
l 2
l 2
o 1

Wrong: l 2 is printed twice, the order is the word's, not the alphabet's, and each count scans the whole word: O(n²).

map vs unordered_map

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
using namespace std;

int main() {
    string s;
    cin >> s;
    unordered_map<char, int> u;
    map<char, int> m;
    for (char c : s) { u[c]++; m[c]++; }
    cout << "unordered_map:";
    for (auto [c, k] : u) cout << " " << c << k;
    cout << "\nmap:          ";
    for (auto [c, k] : m) cout << " " << c << k;
    cout << "\n";
    return 0;
}

Input programming:

unordered_map: i1 m2 n1 a1 g2 o1 r2 p1
map:           a1 g2 i1 m2 n1 o1 p1 r2
Container Inside Order Cost per access
map<char, int> a balanced tree (red-black tree) sorted by key O(log k)
unordered_map<char, int> a hash table none: can differ between compilers, runs or inputs O(1) on average
int cnt[26] 26 boxes a to z O(1), the fastest

(k = the number of different keys.) Never rely on the order of an unordered_map.

The array version

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt[26] = {};
    for (char c : s) cnt[c - 'a']++;
    for (int i = 0; i < 26; i++)
        if (cnt[i] > 0)
            cout << char('a' + i) << " " << cnt[i] << "\n";
    return 0;
}

Input programming:

a 1
g 2
i 1
m 2
n 1
o 1
p 1
r 2

Alphabetical, each letter once. O(n + 26) time, O(1) space.

Complexity summary

Program Time Extra space
anagram, sort both O(n log n) O(n) (copies)
anagram, cnt[26] O(n) O(1)
first unique, nested loops O(n²) O(1)
first unique, map then second pass O(n log k) O(k)
first unique, cnt[26] two passes O(n) O(1)
frequency, count() per character O(n²) O(1)
frequency, map O(n log k) O(k)
frequency, unordered_map O(n) average O(k)
frequency, cnt[26] O(n) O(1)

The pattern: a loop inside a loop that counts something is O(n²). Count once, store the counts, then look them up: O(n).

Common mistakes (and the real results)

Mistake What you see Why Fix
b.find(c) for every c in a aab abb -> anagram it never counts sort, or cnt[26] + length check
no length check cat cats -> anagram extra letters ignored if (a.size() != b.size())
counting inside a loop Time Limit Exceeded n × n count once, then look up
loop over a map for "first" swiss -> i a map is sorted by key second pass over the string
printing an unordered_map letters in any order a hash table has no order map or cnt[26]
cnt[c - 'a'] on capitals or spaces out-of-bounds index (UB) 'A' - 'a' is −32 cnt[256] with (unsigned char)c, or tolower

Your turn: the most frequent letter (solution)

Problem. Print the letter that appears most often in a word; on a tie, the smallest letter.

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        int cnt[26] = {};
        for (char c : s) cnt[c - 'a']++;
        int best = 0;
        for (int i = 1; i < 26; i++)
            if (cnt[i] > cnt[best]) best = i;   // > keeps the smaller letter on a tie
        cout << s << " -> " << char('a' + best) << " (" << cnt[best] << ")\n";
    }
    return 0;
}

Input programming banana abc zzza:

programming -> g (2)
banana -> a (3)
abc -> a (1)
zzza -> z (3)

With >= instead of >, a later letter would win every tie (programming would give r). O(n) time, O(1) space.

Practice questions (with solutions)

1. Ransom note: can the note be made from the letters of the magazine (each letter used once)?

Solution
#include <iostream>
#include <string>
using namespace std;

bool canMake(const string& note, const string& magazine) {
    int cnt[26] = {};
    for (char c : magazine) cnt[c - 'a']++;
    for (char c : note)
        if (--cnt[c - 'a'] < 0) return false;   // needed one more than the magazine has
    return true;
}

int main() {
    string note, magazine;
    while (cin >> note >> magazine)
        cout << note << " from " << magazine << (canMake(note, magazine) ? " -> yes\n" : " -> no\n");
    return 0;
}

Input aa aab chai achhia cat act aab ab:

aa from aab -> yes
chai from achhia -> yes
cat from act -> yes
aab from ab -> no

2. Minimum deletions to make two words anagrams. +1 / −1 tally, then add up the absolute values.

Solution
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

int main() {
    string a, b;
    while (cin >> a >> b) {
        int cnt[26] = {};
        for (char c : a) cnt[c - 'a']++;
        for (char c : b) cnt[c - 'a']--;
        int deletions = 0;
        for (int i = 0; i < 26; i++) deletions += abs(cnt[i]);
        cout << a << " " << b << " -> " << deletions << "\n";
    }
    return 0;
}

Input cde abc chai chat listen silent:

cde abc -> 4
chai chat -> 2
listen silent -> 0

3. Are two sentences anagrams, ignoring spaces, punctuation and case? cnt[256] indexed by tolower((unsigned char)c).

Solution
#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int main() {
    string a, b;
    while (getline(cin, a) && getline(cin, b)) {
        int cnt[256] = {};
        for (char ch : a) { unsigned char c = ch; if (isalnum(c)) cnt[tolower(c)]++; }
        for (char ch : b) { unsigned char c = ch; if (isalnum(c)) cnt[tolower(c)]--; }
        bool same = true;
        for (int i = 0; i < 256; i++)
            if (cnt[i] != 0) same = false;
        cout << "[" << a << "] [" << b << "] -> " << (same ? "anagrams" : "not anagrams") << "\n";
    }
    return 0;
}

Input (pairs of lines: Dormitory / Dirty room, Chai time / Time, chai!, hello / world):

[Dormitory] [Dirty room] -> anagrams
[Chai time] [Time, chai!] -> anagrams
[hello] [world] -> not anagrams

Mini project: a letter report

For each word: the frequency of every letter, and the first unique letter.

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        int cnt[26] = {};
        for (char c : s) cnt[c - 'a']++;
        cout << s << ":";
        for (int i = 0; i < 26; i++)
            if (cnt[i] > 0) cout << " " << char('a' + i) << cnt[i];
        int first = -1;
        for (int i = 0; i < (int)s.size(); i++)
            if (cnt[s[i] - 'a'] == 1) { first = i; break; }
        cout << " | first unique: " << (first == -1 ? string("none") : string(1, s[first])) << "\n";
    }
    return 0;
}

Input swiss programming aabb:

swiss: i1 s3 w1 | first unique: w
programming: a1 g2 i1 m2 n1 o1 p1 r2 | first unique: p
aabb: a2 b2 | first unique: none

Quick quiz

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    string s = "banana";
    map<char, int> m;
    for (char c : s) m[c]++;
    cout << m.begin()->first
         << m['n'] << m.size() << "\n";
    return 0;
}

(A) a23 (B) b23 (C) a26 (D) n32

Answer

(A) a23. The map is sorted, so its first key is a (not b, the first letter of the word). n appears 2 times. There are 3 different letters: a, b, n.

Output:

a23

Interview questions

  1. Check if two strings are anagrams. Can you do better than sorting? Yes: a counting array, O(n) time, O(1) space for a fixed alphabet.
  2. Find the first non-repeating character in O(n). Count in one pass, then a second pass over the string.
  3. Why is iterating a std::map the wrong second pass? It visits keys in sorted order, not in the order they appeared.
  4. map vs unordered_map? Tree, sorted, O(log n) vs hash table, unordered, O(1) average (O(n) worst case).
  5. When is a plain array better than a map? When the keys are small integers in a known range (a to z, 0 to 255): faster and simpler.
  6. What does c - 'a' compute? The position of a small letter in the alphabet (0 to 25).
  7. What is the time complexity of a loop that calls std::count on the whole string? O(n²).
  8. What happens on m['x'] for a key that isn't in a map? It inserts 'x' with value 0 (use find or count to only check).

Glossary

Term Meaning Example
Anagram Same letters, same counts, any order listen / silent
Frequency How many times something appears l appears 2 times in hello
Counting array (frequency array) An array with one counter per possible value int cnt[26]
c - 'a' A small letter's position in the alphabet 'd' - 'a' = 3
char('a' + i) The letter at position i char('a' + 2) = 'c'
std::sort Sorts a range, O(n log n) sort(s.begin(), s.end())
Pass One walk through the data count in pass one, look up in pass two
std::map Key → value container, sorted by key (a balanced tree) map<char, int>
std::unordered_map Key → value container with no order (a hash table) unordered_map<char, int>
Hash table Finds a key by computing a number (hash) from it O(1) average lookup
Structured binding auto [key, value] unpacks a pair (C++17) for (auto [c, k] : m)
std::count Counts a value in a range, O(n) count(s.begin(), s.end(), 'l')
steady_clock A stopwatch clock from <chrono> steady_clock::now()
Pass by value The function gets its own copy bool isAnagram(string a, string b)
O(n²) Work grows with the square of n nested loops over the word
O(n log n) Sorting-speed growth sort
Time Limit Exceeded (TLE) The judge stopped a program that ran too long 8 seconds here

Summary

  • Anagram: sort both (O(n log n)) or a +1 / −1 tally in int cnt[26] with a length check (O(n)). Checking that each letter merely appears is wrong.
  • First non-repeating character: count once, then a second pass over the string. Looping over a map gives the first in the alphabet.
  • Frequency: map (sorted), unordered_map (no order), or int cnt[26] (a to z, fastest). Print a letter with char('a' + i).
  • A loop inside a loop that counts is O(n²): count once, then look up.

Next episode: String questions III: reverse the words of a sentence with stringstream, remove duplicate characters keeping their order, and run-length compression (aaabb → a3b2), plus why s + c in a loop is slow.