vizlearn

Group anagrams together

Interview QuestionsBy Updated

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.

Overview

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.

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."

Group anagrams together

Given a list of words, group the anagrams together.

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.

Run it in Python

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.

group_anagrams.pyPython 3
Output
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
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.
INTERVIEW · vizlearn.in/interview/group-anagrams.html
More in Interview
InterviewLongest substring without repeating charactersInterviewFirst non-repeating characterInterviewValid parenthesesInterviewRun-length string compression
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.
About VizLearnGitHubLinkedInContact