Group anagrams together

Do not compare words with each other. Give each word a canonical key — its letters sorted, or a tuple of letter counts — and use a dictionary to collect words sharing a key. One pass, no pairwise comparison, and the whole O(n²) instinct disappears.

StringsCoding problemMedium

Step through it

What to watch

  • Each word is looked at once and never compared with another word.
  • The key is the group's identity — that is the whole idea.
  • Six words: six lookups here, fifteen comparisons the naive way.

Say this out loud

"Map each word to a canonical form - sorted letters - and group by that in a dict. O(n·m log m) for n words of length m, instead of n² pairwise comparisons."

Overview

Anagrams contain the same characters with the same multiplicities. Give each word a canonical key—such as sorted letters or a fixed-size frequency tuple—and group words that share that key.

In this guide
  1. Run it: Group anagrams together in code
  2. The two canonical forms
  3. Why a tuple, not a list
  4. The instinct, and why it is wrong
  5. Choosing the key
  6. The pattern behind it
  7. Walking through the example
  8. Edge cases
  9. The follow-ups
  10. Sources and next steps

Run it: Group anagrams together in code

Both keys, plus the pairwise version with its comparisons counted, so the difference between six lookups and fifteen comparisons is a number on the screen rather than a claim.

1Python
Output
2Python
Output
3Python
Output

The two canonical forms

Sorted characters:

4Python
Output

O(n × m log m) for n words of length m. Simple, and it is the answer most people give.

Character counts:

5Python
Output

O(n × m) — no sorting. The key is a 26-element tuple rather than a string, which is a fixed-size key regardless of word length.

 Sorted keyCount key
TimeO(n m log m)O(n m)
Key sizem26 (fixed)
Alphabet assumptionNoneLowercase ASCII
ReadabilityBetterWorse

Which is better depends on m. For short words the sort is negligible and the sorted key is clearer; for long words or a large corpus the count key wins. For non-ASCII input the count array must become a dictionary or a Counter, at which point the sorted key is simpler again.

Why a tuple, not a list

groups[counts] with counts as a list raises TypeError: unhashable type: 'list'.

Dictionary keys must be hashable, which requires immutability — if a key could change after insertion, its hash would change and the entry would become unreachable. A tuple is immutable and hashable; a list is not.

That is a small detail and it is one interviewers specifically watch for, because it demonstrates understanding of why the restriction exists rather than merely remembering it.

The same applies to using a Counter as a key: Counter is a dict subclass and therefore unhashable. tuple(sorted(counter.items())) is the usual conversion.

The instinct, and why it is wrong

The obvious approach compares every word with every other word to see whether they are anagrams. That is n(n−1)/2 comparisons, each costing O(m log m) or O(m), so the whole thing is O(n²·m).

The realisation that fixes it: being anagrams is an equivalence relation, so instead of testing pairs you can give every word a label that all its anagrams share, and group by label. Dictionaries group by label in O(1) each.

Choosing the key

Sorted letters. "".join(sorted(word)). Simple, obviously correct, O(m log m) per word. This is the answer to give.

A count tuple. A 26-element tuple of letter counts, built in O(m). Faster for long words, and the improvement to mention when asked. It must be a tuple, not a list — keys have to be hashable.

Total cost is O(n·m log m) with sorting, or O(n·m) with counts. Either way the n² is gone.

The pattern behind it

"Canonicalise, then group" solves a whole family of questions: find duplicate files by hashing contents, group points by slope, detect isomorphic strings by normalising the pattern. Whenever a question asks you to find things that are equivalent under some transformation, look for the canonical form before you look for a clever comparison.

Walking through the example

["eat", "tea", "tan", "ate", "nat", "bat"] with the sorted key:

WordKeyGroups after
eataet{aet: [eat]}
teaaet{aet: [eat, tea]}
tanant{aet: [...], ant: [tan]}
ateaet{aet: [eat, tea, ate], ...}
natant{..., ant: [tan, nat]}
batabt{..., abt: [bat]}

One pass, and the grouping falls out of the dictionary. Note that the output order depends on insertion order, which Python dictionaries preserve — so the groups come out in the order their first member appeared. If the expected output has a specific order, that must be stated.

Edge cases

CaseHandling
Empty inputReturns []
Single wordOne group of one
All words identicalOne group — a word is an anagram of itself
Words of different lengthsDifferent keys automatically
Empty strings in the inputGroup together under the empty key
Duplicate wordsBoth appear in the same group
Mixed caseDifferent keys unless normalised — ask
Non-ASCIICount array breaks; use sorted or a Counter

The mixed-case row is worth raising: "Eat" and "tea" are anagrams under a case-insensitive reading and not under a strict one. Ask.

The follow-ups

"What if the words are very long?" The count key avoids the sort, giving O(m) per word instead of O(m log m).

"What about a huge corpus that does not fit in memory?" Compute the key per word and partition by hash across machines or files — all anagrams share a key, so they land in the same partition. This is a MapReduce shape: the key is the map output, and the grouping is the shuffle.

"Find all anagrams of one word in a list." Compute that word's key once and filter, O(n m). No dictionary needed.

"Find all anagram substrings of a pattern in a longer string." A sliding window of the pattern's length with an incrementally updated count — O(n) rather than re-counting each window.

"What if we want groups sorted by size?" Sort the result by len, which is a one-line addition and a reasonable clarification to offer.

Sources and next steps

How the code works

Both keys, plus the pairwise version with its comparisons counted, so the difference between six lookups and fifteen comparisons is a number on the screen rather than a claim.

How the code works

  1. groups["".join(sorted(w))].append(w)The whole algorithm. Sorting the letters produces a label every anagram of that word shares, and the dictionary does the grouping in O(1).
  2. tuple(counts)Must be a tuple. A list is mutable and therefore unhashable, so it cannot be a dictionary key — the last lines of the program show the exact error.
  3. defaultdict(list)Removes the "is this key here yet?" branch. setdefault does the same job in one line if you would rather not import anything.
  4. group_pairwiseKept only for its comparison count. It is O(n²·m) and the number it prints is the argument against writing it.

Change one thing

  • Add twenty more words and compare the two counts again. Lookups grow linearly, comparisons quadratically.
  • Feed it a word with an accent. The count-tuple version raises — that is the alphabet assumption, and it is worth saying out loud before you offer the optimisation.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

  1. The key idea in grouping anagrams efficiently is:

  2. Why must the count key be a tuple rather than a list?

  3. For n words of length m, grouping by sorted key costs:

Cheat sheet

Group anagrams together

Group words that are anagrams of each other. Sort each word into a canonical key, collect matches in a dictionary, and see the cost of each step.

INTERVIEW · vizlearn.in/interview/group-anagrams.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.