Group Anagrams
Put words that are anagrams of each other into the same group.
- Grouping by a canonical key
- Frequency counting
Before this, know: Valid Anagram (what an anagram is), Hash maps (Map in JavaScript, dict in Python), Sorting a string
You get a list of words called strs. Put the words into groups, so that
two words share a group exactly when they are anagrams of each other: the
same letters, each used the same number of times, in any order (like “eat” and
“tea”). Return the list of groups.
- eat0
- tea1
- tan2
- ate3
- nat4
- bat5
| letters | words |
|---|---|
| aet | [eat, tea, ate] |
| ant | [tan, nat] |
| abt | [bat] |
The rules that matter:
- The groups can come back in any order, and so can the words inside each group.
- A word with no anagram partner still gets a group of its own (like “bat”).
- Words can be empty (
"") and contain only lowercase letters. There can be up to 10,000 words of up to 100 letters each.
So what “address” do all anagrams share? They’re the same letters in a different order. If we put the letters in alphabetical order, every anagram gives the same result: “eat”, “tea” and “ate” all become “aet”. That shared form is called a canonical key: one standard way of writing things that are “the same” for our purposes.
Pause and think
“tan” → “ant”, “nat” → “ant”, “bat” → “abt”. “tan” and “nat” have the same key, so they share a group. “bat” has a different key, so it gets its own.
Without keys, we’d keep a list of groups and, for every word, compare it with the first word of each existing group (using the Valid Anagram check). If it matches, it joins that group; if it matches none, it starts a new one.
Brute force: compare with every group
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
- eat0
- tea1
- tan2
- ate3
- nat4
- bat5
| group | words |
|---|---|
| 0 | [eat] |
- comparisons
- 0
- Looking at now
- Group being compared
- Same letters
"eat" is the first word, so it starts group 0.
Which line is running?
function groupAnagrams(strs) { const sameLetters = (a, b) => [...a].sort().join("") === [...b].sort().join(""); const groups = []; for (const word of strs) { let placed = false; for (const group of groups) { if (sameLetters(group[0], word)) { group.push(word); placed = true; break; } }Running now: if (!placed) groups.push([word]); // no match: start a new group } return groups;}Brute force: compare with every group
function groupAnagrams(strs) { const sameLetters = (a, b) => [...a].sort().join("") === [...b].sort().join(""); const groups = []; for (const word of strs) { let placed = false; for (const group of groups) { if (sameLetters(group[0], word)) { group.push(word); placed = true; break; } } if (!placed) groups.push([word]); // no match: start a new group } return groups;}def group_anagrams(strs): groups = [] for word in strs: placed = False for group in groups: if sorted(group[0]) == sorted(word): group.append(word) placed = True break if not placed: groups.append([word]) # no match: start a new group return groupsplaced is a flag: a true/false variable that remembers whether the word
found a home, so we know whether to start a new group after the inner loop.
Each word may be compared with every group, and with n words there can be up to n groups (if no two are anagrams). That’s up to n × n ÷ 2 comparisons, and each comparison sorts two words. With 6 words that’s at most 15 comparisons. With 10,000 words it’s up to 50,000,000 comparisons, each one sorting two words of up to 100 letters. We describe this growth with Big-O notation, a short way of saying how the work grows as the input grows (see Big-O in 5 minutes). Here it’s O(n² · k log k), where k is the length of a word and k log k is roughly the cost of sorting one word.
The brute force compares words with each other. The fix is to compute, for
each word, a key that’s identical for all of its anagrams, and let a hash map
do the grouping. A hash map is a lookup table from a key to a value (Map in
JavaScript, dict in Python) that finds a key in about one step (see
What is a hash map?).
Pattern
Grouping by a canonical key
Use it when: things that are 'the same' in some sense (anagrams, shifted strings, same shape) must end up together.
Signal words
- “group”
- “anagrams of each other”
- “equivalent”
- “same pattern”
- “bucket these”
- Create an empty hash map
groups. Keys are sorted words; values are lists of words. - For each word, sort its letters to get its
key. - If
keyisn’t in the map yet, add it with an empty list. - Append the word to
groups[key]. - At the end, return all the lists in the map.
Press Play and watch each word compute its key, then flow into its group. Notice that “tan” and “nat” never meet “eat”: they just go to a different key. Then try the edge cases: the empty string, and repeated one-letter words.
Group by a sorted-letters key
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
- eat0
- tea1
- tan2
- ate3
- nat4
- bat5
- word
- —
- key
- —
| key (sorted) | words | |
|---|---|---|
| empty | ||
- Looking at now
- Already grouped
- Key already exists
- New key
- Group just changed
Start with an empty hash map "groups". Its keys will be a word's letters in sorted order; its values will be the list of words that share those letters.
Which line is running?
function groupAnagrams(strs) {Running now: const groups = new Map(); // sorted letters -> the words with those letters for (const word of strs) { const key = [...word].sort().join(""); // "eat" -> "aet" if (!groups.has(key)) groups.set(key, []); groups.get(key).push(word); } return [...groups.values()];}Sorting a word of k letters costs about k × log k. Since the words use only a
to z, there’s an even cheaper key: the word’s 26 letter counts, like the
26-slot array from Valid Anagram. Two words are
anagrams exactly when these counts match.
- a10
- b01
- c02
- d03
- e14
- f05
- g06
- h07
- i08
- j09
- k010
- l011
- m012
- n013
- o014
- p015
- q016
- r017
- s018
- t119
- u020
- v021
- w022
- x023
- y024
- z025
Count signature as the key
function groupAnagrams(strs) { const groups = new Map(); // letter counts -> the words with those counts for (const word of strs) { const count = new Array(26).fill(0); for (const ch of word) count[ch.charCodeAt(0) - 97]++; const key = count.join(","); // "eat" -> "1,0,0,0,1,0,...,1,..." if (!groups.has(key)) groups.set(key, []); groups.get(key).push(word); } return [...groups.values()];}def group_anagrams(strs): groups = {} # letter counts -> the words with those counts for word in strs: count = [0] * 26 for ch in word: count[ord(ch) - ord("a")] += 1 key = tuple(count) # a tuple can be a dict key, a list can't if key not in groups: groups[key] = [] groups[key].append(word) return list(groups.values())A key must be something a hash map can compare by value. In JavaScript an array
is compared by identity (two different arrays never match), so we join the
counts into a string like "1,0,0,0,1,…". In Python a list can’t be a dict key at
all, but a tuple (a read-only list) can, so we use tuple(count).
Hash map keyed by sorted letters
function groupAnagrams(strs) { const groups = new Map(); // sorted letters -> the words with those letters for (const word of strs) { const key = [...word].sort().join(""); // "eat" -> "aet" if (!groups.has(key)) groups.set(key, []); groups.get(key).push(word); } return [...groups.values()];}def group_anagrams(strs): groups = {} # sorted letters -> the words with those letters for word in strs: key = "".join(sorted(word)) # "eat" -> "aet" if key not in groups: groups[key] = [] groups[key].append(word) return list(groups.values())The JavaScript does lines 5–6 of Python on a single line 5, so from there on Python runs one line ahead.
- Line 1: define the function. (LeetCode wraps Python in
class Solutionasdef groupAnagrams(self, strs); JavaScript isvar groupAnagrams = function(strs).) - Line 2: an empty hash map. Each key will be a sorted word; each value a list of words.
- Line 3: visit every word once.
- Line 4: the canonical key. In JS,
[...word]splits the word into letters,.sort()puts them in alphabetical order, and.join("")glues them back into a string. In Python,sorted(word)returns a sorted list of letters and"".join(...)glues them. - Line 5 (JS) / lines 5–6 (Python): the first time we meet a key, give it an empty list, so the next line has something to append to.
- Line 6 (JS) / line 7 (Python): add the word to its group.
- Line 8 (both): the map’s values are the groups.
[...groups.values()]in JS andlist(groups.values())in Python turn them into a plain list.
| word | key | key already in map? | groups afterwards |
|---|---|---|---|
| eat | aet | no: new group | {aet: [eat]} |
| tea | aet | yes | {aet: [eat, tea]} |
| tan | ant | no: new group | {aet: [eat, tea], ant: [tan]} |
| ate | aet | yes | {aet: [eat, tea, ate], ant: [tan]} |
| nat | ant | yes | {aet: [eat, tea, ate], ant: [tan, nat]} |
| bat | abt | no: new group | {aet: […], ant: […], abt: [bat]} |
The answer is the three lists: [["eat","tea","ate"], ["tan","nat"], ["bat"]].
Look at the ate row: “ate” goes straight to the aet group without being compared
with “tan” at all. That’s the time we save.
Here n is the number of words and k is the length of the longest word.
Brute force
Time
O(n² · k log k)
Up to n × n ÷ 2 word comparisons, each sorting two words.
Space
O(n · k)
The groups hold every word.
Sorted letters as key
Time
O(n · k log k)
One sort per word (k log k), then about one step for the map lookup. 10,000 words × ~700 steps ≈ 7 million steps.
Space
O(n · k)
The map stores every word plus one key per group.
Letter counts as key
Time
O(n · k)
Counting a word's letters is k steps, and building the key is 26 steps, a fixed amount.
Space
O(n · k)
Same as above: every word is stored once.
In practice both keyed versions are fast. Sorted keys are shorter to write and easier to explain; the count key is the answer to “can you avoid sorting?”.
What to say out loud, in this order:
- “Anagrams share the same sorted letters, so the sorted word is a canonical key.”
- “A hash map from key to list groups the words in one pass: O(n · k log k).”
- “Since the alphabet is fixed, a 26-count key avoids sorting: O(n · k).”
- Mention the JS array-as-key trap and how you avoid it.
Likely follow-up questions:
- “Can you avoid sorting?” Yes: the count signature (Approach 3).
- “What if the words use any Unicode characters?” Sorted keys still work; for counts, use a hash map of letter → count and turn its sorted entries into a string.
Related problems:
- Valid Anagram (this week): the yes/no version for two words.
- Top K Frequent Elements (this week): another “group things, then use the groups” problem, grouping numbers by their count.
- Two Sum (this week): a hash map from value to index, instead of key to group.