Group anagrams with canonical keys

Why this matters

Many programs sort a pile of items into bins. A shop sorts orders by customer. A spell checker sorts words by the letters they use. This lesson sorts words into bins where every word in a bin is an anagram of the others. An anagram is a word made from the same letters in a different order.

The method has two steps. First, give each word a key that every one of its anagrams shares. Second, put each word into the bin for its key. The key is called a canonical key. Canonical means one standard form that the whole group agrees on. An unordered_map from the earlier lessons holds the bins, so finding a bin takes about the same time on average, however many bins exist.

This lesson uses only string keys. The custom keys lesson shows how to make keys from your own types, and the counted maps lesson covers the same letter-count idea in a different setting.

What an anagram is

Two words are anagrams when they have the same letters, with the same number of each letter. Take the word tea. It has one t, one e and one a. The word eat has the same three letters, so eat is an anagram of tea. The word ate is one too. The word bat is not, because it has a b where tea has an e.

Checking two words for this is easy when you can sort their letters. Sorting tea gives aet. Sorting eat also gives aet. Sorting bat gives abt. Two words are anagrams exactly when their sorted letters match. So the sorted letters can serve as the canonical key.

Here are six words and their sorted keys:

Words with the same key form one group. The aet group is eat, tea and ate. The ant group is tan and nat. The abt group is only bat.

The finished result is a map from each key to its bin. Written out as a picture, it looks like this:

key "aet"  ->  [eat, tea, ate]
key "ant"  ->  [tan, nat]
key "abt"  ->  [bat]

Each bin is a vector<string>, a growable list of words. The map finds a bin from its key, and the vector keeps the words in the order they arrived.

Working one word by hand

Before you write code, it helps to do one word on paper. Take listen. Write its letters in a row: l i s t e n. Sort them into alphabetical order: e i l n s t. Join them and the key is eilnst.

Now take silent. Its letters are s i l e n t. Sorted, they are e i l n s t, the same as before. So listen and silent go into the same bin. Doing one or two words this way is a quick check on a program. If the hand result and the program disagree, the bug is in the key function, not in the map.

First version: sorted letters as the key

The program below reads the six words, builds the key for each one, and puts the word into the bin for that key. The bins are a map from a key string to a vector of words.

The output is:

abt: bat 
aet: eat tea ate 
ant: tan nat 

Each line starts with the key and then lists the words in the order they were read. The word eat came first, so it comes first in its group, and ate comes last.

The program copies each word into key before sorting it. The loop gives the program a const reference to each word, so the word cannot be changed. Sorting a copy leaves the input as it was. The mistakes section shows the error you get when you sort a const word.

The program sorts the keys at the end before printing. That is a choice for the printout only. The unordered_map does not keep its keys in any order, so the bins can come out in a different order between compilers or library versions. The iteration order lesson covers this in detail.

Each word costs about k log k steps to sort, where k is the number of letters in the word. For a word of 5 letters that is a few steps. For a word of 1,000 letters it is far more. The sort runs once per word, so the total cost is about the sum of those sorts over all the words.

Second version: letter counts as the key

Sorting is not the only way to find the same letters. A second method counts how many times each letter appears. Two words are anagrams exactly when their letter counts match. The count table has 26 slots for the letters a to z. Each word fills in its own table in one pass, and the table is then turned into a key string.

The key string must be built carefully. The program below writes each letter that appears, then its count, then a comma. A word such as tea gives a1,e1,t1,. The letters are written in alphabetical order, so the same counts always give the same string.

The output is:

eat -> a1,e1,t1,
tea -> a1,e1,t1,
tan -> a1,n1,t1,
ate -> a1,e1,t1,
nat -> a1,n1,t1,
bat -> a1,b1,t1,
groups: 3

The three words eat, tea and ate all produce a1,e1,t1,. That is the same key, so they share a bin. The program builds 3 bins, the same result as the sorted version.

Look at what the key does not need. It never sorts. It reads each letter once and then checks 26 slots. A word of 1,000 letters still takes about 1,000 steps to count plus 26 steps to write the key. The cost grows with the length of the word, not with the length times its logarithm.

Making the count key safe

A count key has one easy way to go wrong. Suppose you write the 26 counts one after another with no letter names and no separators. That looks shorter, and it seems to work for short words. It fails when a count has two digits. The program below shows two different words that give the same bad key.

The output is:

bad key, first:  111000000000000000000000000
bad key, second: 111000000000000000000000000
same bad key? 1
good key, first:  a1,b11,
good key, second: a11,b1,
same good key? 0

The first word has one a and eleven bs. The second word has eleven as and one b. They are not anagrams, yet the bad key treats them as equal. The count of a is 1 followed by the count of b, which is 11, so the text is 111. The second word writes 11 for a and then 1 for b, which is also 111. The two numbers run together, and the reader cannot tell where one stops.

The good key avoids this. The letter names and the commas mark the edges, so a1,b11, and a11,b1, are different strings. Every count key must have a clear boundary between entries. A letter, a count and a comma is one simple way to do it.

Comparing the two keys

Both keys are correct when they are built with the rules above. They differ in cost and in how they look.

The count key is not always the shorter one. Take banana. Sorting gives aaabnn, which has 6 characters. The count key gives a3,b1,n2,, which has 9 characters. The count key reads each letter once, but its length depends on how many different letters the word uses and how many digits each count needs. It does not depend on the word length alone.

For short words, both keys are fast. A word of 5 to 10 letters makes either approach finish almost at once. The gap appears with long words. A sentence of 10,000 letters costs far less to count than to sort. The sorted key is the better choice when the words are short, because it is simple to write and simple to check by eye. The counts key is the better choice for long text, where the sort is the slow step.

The sorted key also has a useful property. Its characters are the letters of the word in order, so a person can read the key and see which letters the group uses. The count key is harder to read, but it is easier to build from a stream of characters.

Third example: keep only real groups

Now a slightly harder task. Words that have no anagram should be left out, and the groups should be printed from the biggest to the smallest. This program uses the sorted key, and it also counts how many groups were dropped.

The output is:

listen silent enlist (3)
cat act (2)
google gogole (2)
singletons dropped: 1

The function sortedKey takes its argument by value, so it works on its own copy. The word dog is the only one with no anagram in the input, so it is the one dropped. The groups are sorted with a comparison that checks the size first and the first word second. The [](...) part is a lambda, a small function written in place. The second rule makes the output the same on every run, because the bins themselves come out of an unordered_map in no fixed order.

The groups.size() - answer.size() line uses the fact that every group of size one is a bin that was not copied into answer. Both values are counts of bins, so the subtraction gives the number of single-word bins.

Common mistakes

Using the word itself as the key. A beginner may write groups[word].push_back(word). Every word then has its own bin, and no group forms. The program below does exactly that.

The output is wrong key version has 6 groups. Six words gave six bins. The fix is to change the key, not the push. The key must be the sorted letters or the count string.

Assigning a word where a bin is expected. The bin is a vector<string>, not a string. Writing groups[key] = word; tries to store one word where a list of words belongs. The compiler stops with this error from GCC 15, shortened here:

error: no match for 'operator=' (operand types are 'std::vector<std::string>' and 'std::string')

The fix is groups[key].push_back(word);, which adds the word to the list.

Reading a key that is not in the map with at. The method at throws an error when the key is missing. The program below creates one bin and then asks for a key that has no bin.

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
 
int main() {
    unordered_map<string, vector<string>> groups;
    groups["aet"].push_back("tea");
    cout << groups.at("abt").size() << "\n";
}

The program stops with this output from GCC 15's standard library:

terminate called after throwing an instance of 'std::out_of_range'
  what():  unordered_map::at

The map has no abt bin, so at cannot return one. The operator [] would create an empty bin instead, which is what the grouping loop needs. Use at when a missing key is a bug, and [] when a missing key should start a new bin.

Sorting a const string. If the word is declared const, sorting it in place fails. The program below declares word as const and sorts it directly.

#include <algorithm>
#include <string>
using namespace std;
 
int main() {
    const string word = "tea";
    sort(word.begin(), word.end());
}

GCC 15 reports the start of the error like this (the template text is shortened here):

error: assignment of read-only location '__first...operator*()'
error: no matching function for call to 'swap(const char&, const char&)'

The fix is to copy the word into a new string that is not const, as the first example does with string key = word;.

Leaving out the separators in a count key. The collision example in the lesson shows that two different words can give the same key when the counts run together. Always write a letter and a separator, such as a1,, so each count has a clear end.

Using an array as a key. A natural idea is to use the array<int, 26> of counts directly as the key of an unordered_map. This fails to compile. The standard library has no hash function for std::array, so the map cannot find a bin from it. GCC 15 gives this error, with the template text shortened:

error: static assertion failed: hash function must be copy constructible
error: use of deleted function 'std::unordered_map<...>::unordered_map()'

The first line is confusing, because the real problem is the missing hash. Turn the array into a string key, as countKey does. A std::map can use an array as its key, because std::map compares keys with < and does not need a hash. The ordered map is covered in its own lesson.

Practice

Exercise 1. What is the sorted key of the word stop?

Show the answer

The letters of stop in order are o, p, s, t. The key is opst.

Exercise 2. Which of these words are anagrams of dear: read, dare, dears, rated?

Show the answer

read and dare are anagrams. Each has one d, one e, one a and one r. dears has an extra s, and rated has an extra t, so neither is an anagram.

Exercise 3. Which word or words have the count key a2,c1,t1,?

Show the answer

Any word with two as, one c and one t, and no other letters. Examples are taca, acta and caat. Each one produces the same key.

Exercise 4. Why are the count keys a1,b11, and a11,b1, different, while the bad keys 111... are the same?

Show the answer

The bad key writes the counts with no separators, so the digits of two counts can run together. The good key writes a letter and a comma after each count, so 11 in b11, cannot be confused with 1 followed by 1 from another entry.

Exercise 5. What is the count key of banana?

Show the answer

The word has three as, one b and two ns. The count key is a3,b1,n2,.

Exercise 6. How many bins do the words abc, bca and xyz make, and which words are in each?

Show the answer

Two bins. The sorted key of abc and bca is abc, so both words share a bin. The word xyz has the key xyz and gets its own bin. Only the first bin has two words, so a program that keeps only bins with two or more words would keep abc and bca and drop xyz.

Exercise 7. Write one line that adds the word word to the right group, when sortedKey is a function that returns the sorted letters of a string.

Show the answer

groups[sortedKey(word)].push_back(word);

The first part of the line finds the bin for the key. The push_back adds the word to that bin. If the bin does not exist yet, operator[] creates it.

Summary

• Two words are anagrams when they have the same letters with the same counts.
• A canonical key is one shared form for a group, such as the sorted letters or the letter counts.
• Put each word into the bin for its key, using an unordered_map from key to a vector of words.
• Sorting the letters costs about k log k per word. Counting the letters costs about k per word plus a fixed 26 slots.
• A count key must write letters and separators, or two different words can give the same key.
• The map does not keep bins in order, so sort the keys yourself when the printed output must be stable.