Group Anagrams

Two words are anagrams when they use the same letters the same number of times: "listen" and "silent", "eat" and "tea". Grouping anagrams is the standard test of the grouping-map shape, and the whole problem comes down to one design decision: what key do all members of a group share, and no one else?

Get the key right and the code is five lines. Get it wrong and the code is still five lines — it just returns the wrong groups. That is why interviewers like it: the talking matters more than the typing.

The problem

You are given a list of lowercase words. Group together the words that are anagrams of each other and return the groups. The order of the groups, and of the words inside each group, does not matter.

• ["eat", "tea", "tan", "ate", "nat", "bat"] → [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]. The first group all use one a, one e and one t.
• [""] → [[""]]. The empty word is a group of its own.

Constraints: up to 10⁴ words, each up to 100 letters, only a to z.

Clarifying questions

• Only lowercase English letters? Yes. This decides whether a 26-slot count array is safe.
• What if the same word appears twice? Both copies go in the same group.
• Does output order matter? No. (Many judges compare groups in any order; say which order your code produces.)
• Can a word be empty? Yes, and it is a valid group.

Approach 1: compare each word with every group

Keep a list of groups. For each word, compare it with the first word of every existing group using an anagram check. If one matches, join that group; otherwise start a new group.

1def group_anagrams_brute(words: list[str]) -> list[list[str]]:2    """Compare each word with one representative of every existing group."""3    groups: list[list[str]] = []4    for word in words:5        for group in groups:6            if is_anagram(group[0], word):     # the counter check from the core lesson7                group.append(word)8                break9        else:                                  # no group matched10            groups.append([word])11    return groups

Time: O(n · g · L), where g is the number of groups and L the word length. In the worst case every word is its own group, so g grows to n and the cost is O(n² · L). Space: O(n · L) for the output.

With 10⁴ words that are all different, that is about 5 × 10⁷ anagram checks, each reading up to 100 letters — around 5 × 10⁹ character steps. Too slow. And once more, the inner loop is a search: "which group does this word belong to?"

The key insight

Instead of asking "is this word an anagram of that one?", compute a signature for each word: a value that is identical for all anagrams and different for everything else. Then "which group?" is a dictionary lookup on the signature, and there is nothing to compare.

Three candidate signatures:

• Sorted letters. "eat", "tea" and "ate" all sort to "aet". Correct, and O(L log L) per word.
• A count of each letter. A 26-slot tuple: how many a's, how many b's, and so on. Correct, and O(L) per word, plus 26 to build the tuple.
• A product of primes, one prime per letter. Correct in theory, because prime factorisation is unique. In practice the product overflows 64-bit integers for long words in most languages, and it is slower to compute than a count. Mention it, then reject it for that reason — interviewers like seeing an idea weighed and dropped.

Both of the first two keys pass the test that matters: two words get the same key if and only if they are anagrams.

Approach 2: sorted letters as the key

1from collections import defaultdict23def group_anagrams_sorted(words: list[str]) -> list[list[str]]:4    """Key = the word's letters in sorted order."""5    groups: defaultdict[str, list[str]] = defaultdict(list)6    for word in words:7        groups["".join(sorted(word))].append(word)8    return list(groups.values())

sorted(word) returns a list of characters, and "".join(...) turns it back into a string, which can be a key. Dry run on the first example:

Because Python dicts keep insertion order, the output is [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] — groups in the order their first word appeared.

Time: O(n · L log L), from sorting each word. Space: O(n · L) for the keys and the groups.

Approach 3: letter counts as the key

1from collections import defaultdict23def group_anagrams(words: list[str]) -> list[list[str]]:4    """Key = a 26-slot letter count, built in O(L) per word."""5    groups: defaultdict[tuple[int, ...], list[str]] = defaultdict(list)6    for word in words:7        counts = [0] * 268        for character in word:9            counts[ord(character) - ord("a")] += 110        groups[tuple(counts)].append(word)      # a list cannot be a key; a tuple can11    return list(groups.values())

ord(character) - ord("a") maps a to 0, b to 1, up to z at 25. The counts are built in a list, because a list can be changed, and then frozen into a tuple, because only an unchanging value can be a key. For "eat", the key has 1 in slots 0 (a), 4 (e) and 19 (t) and 0 everywhere else.

Time: O(n · (L + 26)), which is O(n · L). Space: O(n · L) for the output, plus 26 integers per distinct key.

Which is faster in practice? The bound says counting. The stopwatch says it depends on L. We timed both on 10,000 random words in CPython: with 5-letter words the sorted key took about 4 ms and the count key about 7 ms, because sorted runs in C while the counting loop runs in Python. With 100-letter words the order flipped: about 86 ms for sorting versus 46 ms for counting. State the bounds, then say that for short words the difference is small and either key is fine.

Edge cases

• Empty word: sorted key "", count key all zeros. Both group empty words together.
• Duplicate words: ["ab", "ab"] gives one group [["ab", "ab"]]; nothing is lost.
• Single word, or empty input: one group, or an empty list.
• Characters outside a–z: the count key breaks. An uppercase "A" gives index −32 and raises IndexError. Worse, "Z" gives −7, which Python quietly reads as slot 19 (the letter t), so ["Z", "t"] comes back as one group. The sorted key works for any characters. If the input is not guaranteed lowercase, use sorted letters or a Counter frozen into a sorted tuple of pairs.

Follow-ups

• Just two words (Valid Anagram): the frequency counter from the core lesson, O(L) time and O(1) space for 26 letters.
• Find every place in a long text where an anagram of a short word starts: a fixed-size sliding window with letter counts, updated in O(1) per step. The Sliding Windows section covers it.
• Group by a different equivalence: the same grouping map with a different key. Strings with the same repeat pattern use the first-seen pattern from Isomorphic Strings. Strings that are shifts of each other ("abc", "bcd", "xyz") use the tuple of gaps between neighbouring letters, taken mod 26.