Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Group Anagrams

Group words that use exactly the same letters by giving every anagram the same hash map key: either its sorted letters or its letter counts.

mediumPattern: Hashing

Updated Medium read: 6 min read

Approaches at a glance

ApproachTimeSpace
Sorted letters as the keyO(n·k log k)O(n·k)
Letter counts as the keyO(n·k)O(n·k)

The problem

Two words are anagrams if one can be made by rearranging the letters of the other, using every letter exactly once: "listen" and "silent", for example. Given a list of words made of lowercase English letters, collect the anagrams into groups. The groups can be returned in any order.

["eat", "tea", "tan", "ate", "nat", "bat"]
    →  [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
 
[""]    →  [[""]]
["a"]   →  [["a"]]

In the complexity figures, n is the number of words and k is the length of the longest word.

The idea: one key per group

The slow way is to compare every word with every other word. That is about n² comparisons, each of which has to look at all the letters.

Hashing removes the comparisons. Suppose there were a function that turned a word into a key, such that two words get the same key exactly when they are anagrams. Then one pass is enough: work out each word's key and drop the word into a hash map bucket under that key. Each bucket is one group.

The whole problem is choosing that key. There are two good choices.

Approach 1: sorted letters as the key

Anagrams contain the same letters in a different order, so putting the letters in alphabetical order makes them identical. "eat", "tea" and "ate" all become "aet".

JavaScript

function groupAnagrams(words) {
  const groups = new Map();
 
  for (const word of words) {
    const key = [...word].sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

Python

def group_anagrams(words):
    groups = {}
 
    for word in words:
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    return list(groups.values())

Walkthrough

["eat", "tea", "tan", "ate", "nat", "bat"]:

Word Key Map after this word
eat aet aet → [eat]
tea aet aet → [eat, tea]
tan ant aet → [eat, tea], ant → [tan]
ate aet aet → [eat, tea, ate], ant → [tan]
nat ant aet → [eat, tea, ate], ant → [tan, nat]
bat abt aet → [eat, tea, ate], ant → [tan, nat], abt → [bat]

A JavaScript Map remembers the order in which keys were added, so the groups come out in the order their first word appeared.

Time O(n·k log k): each of the n words is sorted, which costs O(k log k). Space O(n·k): every word is stored once in the map, along with its key.

Approach 2: letter counts as the key

Sorting does more work than is needed. Two words are anagrams exactly when they contain the same number of each letter, and counting letters takes one pass over the word with no sorting at all.

Count how many times each of the 26 letters appears, then join the 26 counts into a string to use as the key.

JavaScript

function groupAnagramsByCount(words) {
  const groups = new Map();
 
  for (const word of words) {
    const counts = new Array(26).fill(0);
    for (const ch of word) {
      counts[ch.charCodeAt(0) - 97]++;
    }
 
    const key = counts.join("#");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

Python

def group_anagrams_by_count(words):
    groups = {}
 
    for word in words:
        counts = [0] * 26
        for ch in word:
            counts[ord(ch) - ord("a")] += 1
 
        # A tuple can be a dictionary key, so no joining is needed.
        key = tuple(counts)
        groups.setdefault(key, []).append(word)
    return list(groups.values())

97 is the character code of "a", so "a" lands in slot 0, "b" in slot 1, and so on up to "z" in slot 25.

Time O(n·k): each letter of each word is visited once, and building a key from 26 counts is a fixed cost. Space O(n·k).

Why the separator matters

The counts are joined with # rather than being run together. Without a separator, different sets of counts can produce the same text.

Take a word with one b and ten ds, and another with ten bs and one c. Their first four counts are:

Word a b c d Joined with nothing Joined with #
b + ten d's 0 1 0 10 01010… 0#1#0#10#…
ten b's + c 0 10 1 0 01010… 0#10#1#0#…

With nothing between the numbers, both keys read 01010 followed by zeros, and two words that are not anagrams end up in the same group. The bug only shows once a count reaches 10, so short test words will not reveal it.

Which to choose

Sorted key Count key
Code Shortest, hard to get wrong A little longer
Cost per word O(k log k) O(k)
Works for any characters Yes Only a known, small alphabet
Best when Words are short, which is the usual case Words are very long

For ordinary words the sorted key is fast enough and is the clearer answer. The count key is the one to mention when asked whether the sort can be avoided.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

const words = ["eat", "tea", "tan", "ate", "nat", "bat"];
console.log(groupAnagrams(words)); // [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Python

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))  # [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

The comment after each line is the result you should see.

Common mistakes

  • Using an array as a map key. A Map compares arrays by identity, not by contents, so two separate arrays with the same counts are different keys and every word gets its own group. Turn the key into a string first.
  • Joining counts with no separator. See the table above.
  • Forgetting the empty string. "" is a valid word. Its sorted key is "", and it belongs in a group of its own or with other empty strings.
  • Comparing sums or products of character codes. Different sets of letters can add up to the same total, so this groups words that are not anagrams.

Original problem: LeetCode 49: Group Anagrams