Group Anagrams

Put words with the same letters into the same group.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Group Anagrams: Use each word's 26-letter frequency tuple as its bucket address.

Input and goalPut words with the same letters into the same group.

Initialize the group mapThe map is empty and the fresh 26-count array for "eat" is all zeros.

eat[0]e0a1t2|3t4e5a6|7t8a9n10

examplewords = ["eat", "tea", "tan"]mapLabel26-count tuple -> bucketcountsa0 e0 t0; every other letter 0

26-count tuple -> bucketempty

Recognize it

Many lowercase words must be partitioned by equal letter multiplicities while their original letter order is irrelevant.

Keep true

After each word, every processed word appears once in the bucket keyed by its exact 26-count tuple; two words share a bucket exactly when they are anagrams.

Reuse it

Canonicalize each item into an equality-preserving key, then group by that key; this transfers to shifted-string groups, normalized records, and equivalence-class indexing.

Pattern: Hash map with a shared key.

Simple idea: Count each lowercase letter. Anagrams have the same 26 counts, so they use the same tuple as a map key.

from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
   groups: dict[tuple[int, ...], list[str]] = defaultdict(list)
   for word in words:
      counts = [0] * 26
      for char in word:
         counts[ord(char) - ord("a")] += 1
      groups[tuple(counts)].append(word)
   return list(groups.values())

Cost: $O(nm)$ time and $O(nm)$ space for $n$ words of average length $m$.