Top k most frequent words with unordered_map and a custom sort — interview question

Read a block of text and print the k most frequent words.

A word is a maximal run of English letters (A–Z, a–z). Everything else (digits, punctuation, apostrophes, hyphens) separates words.
Words are case-insensitive: count The and THE as the.
Sort by count (highest first). Break ties alphabetically.
If there are fewer than k distinct words, print them all.

Constraints

1 ≤ k ≤ 1000
The text has at most 20000 characters and at least one letter.

Input and output

Input: First line: k. The remaining lines are the text.
Output: Up to k lines, each `word count`.

Examples

Input 1

3
The mess food is good. The lab is open;
the LAB closes at 9.

Output

the 3
is 2
lab 2

"the" appears 3 times. "is" and "lab" both appear twice; "is" comes first alphabetically.

Input 2

2
it's a well-known fact

Output

a 1
fact 1

The apostrophe and the hyphen split words, so we get it, s, a, well, known, fact, each once. The two alphabetically first are printed.

Show hints

std::unordered_map<std::string, int> counts in expected O(1) per word.
Copy the map into a vector<pair<string,int>> and call std::sort with a lambda comparator.
std::tolower takes an int. Cast char to unsigned char before calling it.

Show the explanation

Tokenise. Read character by character. While isalpha is true, append the lower-cased letter to the current word. At any other character, finish the current word (if it is not empty) and do ++freq[word]. Remember to finish the last word at end of input.
Sort. Move the map entries into a vector and sort with

```cpp
[](const auto &a, const auto &b) {
return a.second != b.second ? a.second > b.second : a.first < b.first;
}
```
A comparator must be a strict weak ordering. Use > and <, never >=, or std::sort has undefined behaviour.

Print the first min(k, size) entries.

Counting costs O(L) for text of length L. Sorting the d distinct words costs O(d log d). If d is huge and k is small, std::partial_sort (or a size-k heap) brings that down to O(d log k). Mentioning this is a good follow-up.

Why `unsigned char`? Passing a negative char (any byte above 127 on platforms where char is signed) to tolower or isalpha is undefined behaviour.

Original UniCircle question. Last reviewed 22 Oct 2026.