Group anagrams: cluster a list of strings into anagram groups

TL;DR: Map each string to a canonical key shared by all its anagrams (sorted characters, or a 26-length count tuple), bucket by that key in a defaultdict, and return the buckets.

How to approach it The whole problem is one insight: anagrams share a canonical form. Map each string to a key that's identical for all its anagrams, bucket by that key, return the buckets. Say that sentence first, then discuss key choices: sorted string ("eat" -> "aet") or a character-count tuple. Clarify case sensitivity and whether Unicode/spaces matter. In real FDE work (deduping customer records, normalizing search queries) the normalization step is where bugs live.

A strong answer defaultdict with a sorted-string key is the cleanest version:

from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

Complexity: O(n · k log k) for n words of length k. Then volunteer the alternative: counting characters gives O(n · k):

def group_anagrams_counts(words: list[str]) -> list[list[str]]:
    groups: dict[tuple, list[str]] = defaultdict(list)
    for w in words:
        counts = [0] * 26
        for ch in w:
            counts[ord(ch) - ord("a")] += 1
        groups[tuple(counts)].append(w)   # tuples are hashable; lists aren't
    return list(groups.values())

State the tradeoff honestly: for typical word lengths the sorted key is simpler and just as fast in practice; the count key wins on long strings but hard-codes the alphabet, which breaks on Unicode. Picking the simple one and explaining why reads senior.

The two ways to build the canonical key for a word of length k:

If the bucketing feels abstract, watch the dictionary grow on the standard input (traced by running the code):

One pass, no comparisons between strings, ever: each word computes its own key and files itself. That is the property that makes the canonical-key move scale, and it is the same move you will use on real engagements under the name entity resolution: deduping "ACME Corp.", "Acme Corporation" and "acme corp" means designing a normalization function (lowercase, strip punctuation and legal suffixes) whose output is the canonical key, then bucketing exactly as here. The judgment call that does not exist in the interview version but dominates the real one: too little normalization leaves duplicates apart, too much merges genuinely different entities ("Delta Airlines" and "Delta Dental" both reduce to "delta" if you strip too greedily), and the second failure is far more expensive to unwind.

Tests, unprompted:

out = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
assert sorted(map(sorted, out)) == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
assert group_anagrams([]) == []
assert group_anagrams([""]) == [[""]]      # empty string is its own group
assert group_anagrams(["a"]) == [["a"]]

What interviewers probe next (1) Case-insensitive, ignore punctuation? Add a normalize step (w.lower(), strip non-letters) before keying, keeping it a separate function so the grouping logic doesn't change. (2) Streaming input / too big for memory? The key idea survives: shard by canonical key (it's a stable hash), group within shards. This is a baby MapReduce and saying so scores. (3) Top-K largest groups? heapq.nlargest(k, groups.values(), key=len), a natural bridge to the top-K questions later in most loops.

Common mistakes Using a list as a dict key (unhashable: you'll hit a TypeError live; tuples fix it). Comparing every pair of strings, O(n²k), instead of canonical keys. Burning minutes on the 26-letter count optimization before a working version exists; finish simple, then optimize if asked. And not asking about normalization: "Eat" vs "eat" silently landing in different groups is precisely the kind of data-quality bug FDE interviewers love to see you anticipate.