Group Anagrams

Interview Prep

Warm-upArrays & Hashingstringshashmap

The problem

Given an array of strings, group the anagrams together. The output order doesn't matter; nor does the order within each group.

Pattern: canonical key, then group by key

Anagrams are equivalent under "permutation." We need a function key(s) that returns the same thing for any two anagrams and different things for non-anagrams. Then a single pass with a dict of key → list does the rest.

Solution 1 — sorted-string key

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    buckets: dict[str, list[str]] = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        buckets[key].append(s)
    return list(buckets.values())

Time O(n · k log k) where n is the number of strings and k is the average length. Space O(nk). The shortest possible code; usually the best answer in a screening round.

Solution 2 — count-tuple key

def group_anagrams(strs: list[str]) -> list[list[str]]:
    buckets: dict[tuple[int, ...], list[str]] = {}
    for s in strs:
        counts = [0] * 26
        for c in s:
            counts[ord(c) - ord('a')] += 1
        key = tuple(counts)
        buckets.setdefault(key, []).append(s)
    return list(buckets.values())

Time O(n · k). Space O(nk). Avoids the per-string sort. Useful if strings are very long; the count-tuple is also a more honest representation of "this is a multiset" than the sorted string.

Edge cases

Related