Group Anagrams: Sorted Key vs Letter-Count Key, Explained

"Given a list of words, group the anagrams together." The first idea most people have is to compare words with each other, and that is where the time goes. The better idea never compares two words at all: it computes one key per word that every anagram shares, and lets a hash map do the grouping. The whole problem is choosing that key.

The problem it solves

Given ["eat", "tea", "tan", "ate", "nat", "bat"], return the groups ["eat", "tea", "ate"], ["tan", "nat"] and ["bat"]. Two words are anagrams when they use the same letters the same number of times, in any order. The order of the groups, and of words inside a group, usually does not matter.

The pairwise approach works: for each word, check it against a representative of every group found so far, and join the first group that matches. But with n words that is up to n² comparisons, and each comparison is itself a letter count. With many distinct groups it slows down badly.

The intuition

Instead of asking "is this word an anagram of that one?", ask "what does this word look like with the order thrown away?" If two words produce the same answer, they are anagrams; if they are anagrams, they produce the same answer. A value with that two-way property is a canonical form, and it makes a perfect dictionary key.

Two canonical forms are standard:

• The sorted letters. "eat", "tea" and "ate" all sort to "aet". Easy to write and easy to explain.
• The letter counts. A tuple of 26 numbers, one per letter of the alphabet. "eat" has one a, one e, one t and zeros everywhere else, and so does every anagram of it.

Both keys are exact: equal keys mean anagrams and nothing else. That is the property to check whenever you invent a key of your own.

Watch it run

The animation groups the lesson's ["listen", "silent", "enlist", "google"]. Each word is sorted into its signature, and the signature picks the bucket. The first word creates the eilnst bucket, the next two land in it without ever being compared with listen, and google gets a bucket of its own. The comparison counter stays at zero the whole way through.

The code

The sorted-key version. defaultdict(list) creates an empty group the first time a key is seen:

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)   # key: the letters, sorted
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
print(group_anagrams([""]))                    # [['']]

The count-key version, for lowercase English letters. A list cannot be a dictionary key because it is mutable, so the counts are frozen into a tuple:

def group_anagrams_count(words):
    groups = defaultdict(list)
    for w in words:
        count = [0] * 26
        for ch in w:
            count[ord(ch) - ord("a")] += 1
        groups[tuple(count)].append(w)          # key: 26 letter counts
    return list(groups.values())

print(group_anagrams_count(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

A key that is not canonical, for contrast. Summing character codes gives anagrams the same number, but it also gives unrelated words the same number:

def bad_key(w):
    return sum(ord(ch) for ch in w)             # a sum forgets which letters

print(bad_key("ad"), bad_key("bc"))             # 197 197

Both real versions checked against the pairwise brute force on 3,000 random word lists over a three-letter alphabet, where anagrams and near-misses are common. Python dictionaries keep insertion order, so even the group order matches:

import random
from collections import Counter

def brute_force(words):
    groups = []
    for w in words:
        for g in groups:
            if Counter(g[0]) == Counter(w):     # compare with each group
                g.append(w)
                break
        else:
            groups.append([w])
    return groups

random.seed(4)
ok = True
for _ in range(3000):
    words = ["".join(random.choice("abc") for _ in range(random.randint(0, 4)))
             for _ in range(random.randint(0, 10))]
    expected = brute_force(words)
    ok &= group_anagrams(words) == expected
    ok &= group_anagrams_count(words) == expected
print(ok)                                       # True

The complexity

Let n be the number of words and k the length of the longest one.

• Sorted key: each word is sorted once, O(k log k), so the total is O(n · k log k). Building and hashing the key string is O(k), which the sort already dominates.
• Count key: each word is scanned once, O(k), and the tuple has a fixed 26 entries, so the total is O(n · k). That is asymptotically better, but for short words the fixed cost of building a 26-entry tuple can outweigh the log factor. Measure before claiming it is faster in practice.
• Space: O(n · k) for the groups and keys, since every word is stored once.

The pairwise brute force, by contrast, can reach O(n² · k) when most words end up in different groups.

Where it goes wrong

• A lossy key. Sums, products, or XOR of character codes all collide for words that are not anagrams, as "ad" and "bc" show. A key must describe the multiset of letters exactly.
• A list as a key. groups[count] with a list raises TypeError: unhashable type. Convert it with tuple(count).
• Assuming lowercase ASCII. The count key only works for the alphabet it counts. Uppercase letters, digits or accented characters index outside the 26 slots or silently collide. The sorted key works for any characters, so it is the safer default when the input is not specified.
• Forgetting the empty string. "" is a valid word, and it is an anagram of every other "". Both versions group it correctly because its key is simply empty.

How to say it in an interview

"Instead of comparing words pairwise, I give every word a canonical key that anagrams share and nothing else does, then group by it in a hash map. Sorting the letters is the simplest key, O(k log k) per word, so O(n · k log k) total. If the alphabet is fixed, like lowercase English, a tuple of 26 letter counts brings it to O(n · k). Space is O(n · k) for the output. The one thing I'd check is that the key is exact: a sum of character codes would merge words that are not anagrams."

The same "one key per item, then bucket" move is behind frequency counting, and the hash table basics lesson explains why the lookup itself is constant time on average.