Group Anagrams

The problem

You are given a list words. Call its length n. Put the words into groups, so that two words share a group exactly when they are anagrams of each other. Return the groups.

Two words are anagrams when they use the same letters the same number of times, in any order. The groups, and the words inside each group, may come back in any order.

Example 1

Input: words = ["arc", "dog", "car", "god", "act"]

Output: [["arc", "car"], ["dog", "god"], ["act"]]

“arc” and “car” use a, c and r. “dog” and “god” use d, g and o. “act” has a t, so it stands alone.

words

arc0dog1car2god3act4

Example 2

Input: words = ["", "b", ""]

Output: [["", ""], ["b"]]

The two empty words have the same letters (none), so they are anagrams of each other.

Example 3

Input: words = ["x"]

Output: [["x"]]

One word makes one group.

Constraints

• 1 ≤ n ≤ 10,000
• 0 ≤ words[i].length ≤ 100. Below, k is the length of the longest word.
• Every word holds only lowercase English letters.

Clarifying questions

Does the order of the groups matter?

No. Any order of groups, and of words inside a group, is accepted.

Can a word be empty?

Yes. All empty words form one group together.

Can the same word appear twice?

Yes. Both copies go into the same group.

Which letters can appear?

Only a to z. That is why 26 counters are enough for the count key.

Spot the pattern

We need to put together things that are “the same” under some rule. The trick is to turn each word into a key that is equal for all anagrams and different otherwise. Then a hash map from key to group does the grouping in one pass. That is the hashing pattern.

Solutions

Sorted keyO(n · k log k)Count keyO(n · k)

Show all

This problem has two approaches. Comparing every word with every group also works, but it costs O(n² · k) and is no simpler than the sorted key.

Sorted key O(n · k log k)

The idea

Sort the letters of each word. Anagrams hold the same letters, so they sort into the same string. Words that are not anagrams sort into different strings.

So the sorted word is a perfect key. Keep a hash map from key to a list of words. For each word, build its key and add the word to that key’s list. At the end, the lists are the groups.

Walkthrough

words

arc0dog1car2god3act4

groups

empty

1. groups = defaultdict(list)
2. for word in words:
3. key = "".join(sorted(word))
4. groups[key].append(word)
5. return list(groups.values())

Start with an empty hash map from key to group. Words that share a key are anagrams.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sorted key: anagrams sort into the same string, so it can be a map key.
    // n words of length up to k: O(n * k log k) time, O(n * k) memory.
    public List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String word : words) {
            // Two words are anagrams exactly when their sorted letters match.
            char[] letters = word.toCharArray();
            Arrays.sort(letters);
            String key = new String(letters);
            groups.computeIfAbsent(key, newKey -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }
}

Big O

Time O(n · k log k)Space O(n · k)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The loop runs once per word. Inside it, the sort is the costly line: sorting k letters takes about k × log₂ k steps. Adding the word to the map is about 1 step, plus hashing the key, which reads its k letters.

   1. groups = defaultdict(list)
   2. for word in words:
   3. key = "".join(sorted(word))
   4. groups[key].append(word)
   5. return list(groups.values())

2. 2 Count the runs on Example 1

   Example 1 has 5 words of 3 letters each. Each sort takes about 3 × log₂ 3 ≈ 5 steps. So the loop does about 5 × 5 ≈ 25 steps of sorting in total.

   word	arc	dog	car	god	act
   sort cost (k = 3)	3 × log₂ 3 ≈ 5	3 × log₂ 3 ≈ 5	3 × log₂ 3 ≈ 5	3 × log₂ 3 ≈ 5	3 × log₂ 3 ≈ 5
   map insert	1	1	1	1	1

   total

   5 words × about 5 steps ≈ 25

3. 3 Write the count for any n

   With n words of up to k letters, each word costs one sort plus reading its key once:

   n × (k log k + k)

   Check it with Example 1: 5 × (about 5 + 3) ≈ 40 steps.

4. 4 Keep only the part that grows fastest

   • Drop the + k inside. For longer words, k log k grows faster than k, so the sort is the bigger part of each word’s cost.

   What is left is n · k log k. Two sizes stay in the answer, because the number of words and their length can grow on their own.

   So the time is O(n · k log k).

5. S Space: count the extra memory the same way

   The map ends up holding every word once, plus one key per group. That is at most n × k letters in total. The space is O(n · k). The output itself needs that much anyway.

   groups (all n words)key (k letters)word

Count key O(n · k)

The idea

Sorting is more work than needed. Two words are anagrams exactly when each letter appears the same number of times in both. So count the letters instead: 26 counters, one pass over the word.

Use the list of 26 counts as the key. “arc” and “car” both give one a, one c and one r, so their keys match. “act” gives a t instead of an r, so its key differs.

Why it is correct: the count key is equal exactly when the letter counts are equal, and that is the definition of an anagram.

Walkthrough

words

arc0dog1car2god3act4

groups

empty

1. groups = defaultdict(list)
2. for word in words:
3. count = [0] * 26
4. for letter in word:
5. count[letter] += 1
6. key = tuple(count)
7. groups[key].append(word)
8. return list(groups.values())

Start with an empty hash map from key to group. Words that share a key are anagrams.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Count key: anagrams have the same 26 letter counts, so use them as the key.
    // n words of length up to k: O(n * k) time, O(n * k) memory.
    public List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String word : words) {
            // Counting is one pass over the word, with no sort.
            int[] count = new int[26];
            for (char letter : word.toCharArray()) count[letter - 'a']++;
            // Turn the counts into a string, so it can be a map key.
            String key = Arrays.toString(count);
            groups.computeIfAbsent(key, newKey -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }
}

Big O

Time O(n · k)Space O(n · k)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are two loops: one over the words, and one over the letters of each word. Each inner run adds 1 to one counter, which is 1 step. After that, building and hashing the key reads all 26 counts, which is 26 steps per word.

   1. groups = defaultdict(list)
   2. for word in words:
   3. count = [0] * 26
   4. for letter in word:
   5. count[letter] += 1
   6. key = tuple(count)
   7. groups[key].append(word)
   8. return list(groups.values())

2. 2 Count the runs on Example 1

   Example 1 has 5 words of 3 letters each. Each word costs 3 counting steps plus 26 steps for the key.

   5 × (3 + 26) = 145 steps. For short words the 26 is the bigger part.

   word	arc	dog	car	god	act
   letters counted	3	3	3	3	3
   key built	26	26	26	26	26

   total

   5 × (3 + 26) = 145

3. 3 Write the count for any n

   With n words of up to k letters:

   n × (k + 26)

   Check it with Example 1: 5 × (3 + 26) = 145.

4. 4 Keep only the part that grows fastest

   • Drop the 26. It is a fixed number that never grows. As words get longer, k takes over.

   What is left is n · k. That is the best possible: we have to read every letter of every word at least once.

   So the time is O(n · k).

5. S Space: count the extra memory the same way

   The map holds every word once, plus one 26-number key per group. That is O(n · k). The count array is 26 numbers and is reused for each word.

   groups (all n words)count (26 numbers)keywordletter

Common mistake

Using a list as a map key

In Python, a list cannot be a dictionary key, and in Java two different int[] arrays never count as equal keys, even with the same numbers. Turn the counts into something compared by value: a tuple in Python, a string in Java, C# and TypeScript, or a fixed-size array in Go.

Tested at the limits

2,000 random lists of 1 to 8 words, each up to 3 letters from a and b, empty words included, so many words land in the same group. The sorted key and the count key gave the same groups every time.

Largest inputs	Result
10,000 words of 100 letters (the most allowed), half of them shuffled copies of the other half, so 5,000 groups. Count key.	0.05 s, and about 2 MB of extra memory: one key of 26 counts for each group, which is the O(n) space.