Bundle Anagram Families
MediumArrays & Hashing
Problem
A crossword editor keeps a list of candidate words and wants them grouped so that words using exactly the same letters (with the same multiplicities) end up in the same bundle.
Given words, return a list of bundles, each bundle being a list of words that are rearrangements of each other. Every word goes in exactly one bundle, duplicates included. Bundles and the words inside them may be returned in any order.
Example 1
- Input:
- words = ["listen", "silent", "enlist", "google", "gogole", "cat", "act"]
- Output:
- [["listen", "silent", "enlist"], ["google", "gogole"], ["cat", "act"]]
Each bundle shares one multiset of letters; for example cat and act both use a, c, t once.
Example 2
- Input:
- words = ["a"]
- Output:
- [["a"]]
Constraints
- 1 ≤ words.length ≤ 10^4
- 0 ≤ words[i].length ≤ 100
- words[i] contains only lowercase English letters.
Hint
Show the first hint
Two words belong together when they would look identical after some normalisation. What normalisation?
Walkthrough
How to approach it
01Clarify before coding
- Is the output order important? No, neither the bundles nor the words inside them.
- Are duplicate words kept? Yes, each occurrence goes into its family's bundle.
- Can a word be empty? Yes; all empty strings form one bundle.
02Brute force
For each word, compare it against one representative of every bundle built so far with an anagram check, and open a new bundle if none matches.
Cost: O(n² · L) time in the worst case (every word in its own bundle): 10^8 · 100 for n = 10^4, too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.