Skip to content
16-Week DSA Roadmap
LeetCode #49MediumProblem 4 of 8

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

The problem in plain English

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.

strs
  1. eat0
  2. tea1
  3. tan2
  4. ate3
  5. nat4
  6. bat5
groups3 items
letterswords
aet[eat, tea, ate]
ant[tan, nat]
abt[bat]
Six words, three groups: {eat, tea, ate}, {tan, nat} and {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.

Before you code: think it through

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

What is the sorted key of 'tan'? Of 'nat'? Of 'bat'? Which of them will share a group?

Approach 1: Brute force

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

strs
  1. eat0
  2. tea1
  3. tan2
  4. ate3
  5. nat4
  6. bat5
groups1 item
groupwords
0[eat]
variables
comparisons
0
  • Looking at now
  • Group being compared
  • Same letters

"eat" is the first word, so it starts group 0.

Step 1 / 14

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 groups

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

Why is it slow?

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 pattern: grouping by a canonical key

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

Template

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”

Approach 2: Hash map keyed by sorted letters

  1. Create an empty hash map groups. Keys are sorted words; values are lists of words.
  2. For each word, sort its letters to get its key.
  3. If key isn’t in the map yet, add it with an empty list.
  4. Append the word to groups[key].
  5. 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"]

strs
  1. eat0
  2. tea1
  3. tan2
  4. ate3
  5. nat4
  6. bat5
variables
word
—
key
—
groups0 items
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.

Step 1 / 20

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()];}

Approach 3: Letter counts as the key

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.

count for 'eat'
  1. a10
  2. b01
  3. c02
  4. d03
  5. e14
  6. f05
  7. g06
  8. h07
  9. i08
  10. j09
  11. k010
  12. l011
  13. m012
  14. n013
  15. o014
  16. p015
  17. q016
  18. r017
  19. s018
  20. t119
  21. u020
  22. v021
  23. w022
  24. x023
  25. y024
  26. z025
The count signature of 'eat': one a (slot 0), one e (slot 4), one t (slot 19), zero of everything else. 'tea' and 'ate' produce exactly the same 26 numbers.

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

The code, line by line

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 Solution as def groupAnagrams(self, strs); JavaScript is var 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 and list(groups.values()) in Python turn them into a plain list.

Dry run

wordkeykey already in map?groups afterwards
eataetno: new group{aet: [eat]}
teaaetyes{aet: [eat, tea]}
tanantno: new group{aet: [eat, tea], ant: [tan]}
ateaetyes{aet: [eat, tea, ate], ant: [tan]}
natantyes{aet: [eat, tea, ate], ant: [tan, nat]}
batabtno: new group{aet: […], ant: […], abt: [bat]}
strs = ["eat", "tea", "tan", "ate", "nat", "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.

Complexity

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?”.

Common mistakes and edge cases

What to say out loud, in this order:

  1. “Anagrams share the same sorted letters, so the sorted word is a canonical key.”
  2. “A hash map from key to list groups the words in one pass: O(n · k log k).”
  3. “Since the alphabet is fixed, a 26-count key avoids sorting: O(n · k).”
  4. 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.