Problem 4.4 · HashingMedium

Group Anagrams

PatternFrequency Counting Hash Map Lookup (Complement)

What it teaches: Grouping by a computed key: equivalent items must produce the same key, different items different keys.

Practise it on judges as “Group Anagrams”.

The problem

Given an array of strings strs, group the anagrams together. Return the groups in any order; the words inside a group may be in any order.

Example 1

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

Example 2

Input: strs = [""]
Output: [[""]]

Constraints

1 ≤ strs.length ≤ 10⁴
0 ≤ strs[i].length ≤ 100
Lowercase English letters

Pattern clues in the wording

→ "Group" items that are equivalent
→ Equivalence = same letters, so a canonical key exists

These clues point to Frequency Counting: Count how many times each value appears (with an int[26] or a HashMap), then answer from the counts.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        return new ArrayList<>(groups.values());
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	strs = ["eat","tea","tan","ate","nat","bat"]	[["bat"],["nat","tan"],["ate","eat","tea"]]
2	strs = [""]	[[""]]
3	strs = ["a"]	[["a"]]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Sorted letters as the key · O(n · k log k) for n words of length up to k 2. Optimal: letter counts as the key · O(n · k)

Sorted letters as the key

Time O(n · k log k) for n words of length up to k Space O(n · k)

Sort each word's letters to get its key ("tea" → "aet"). Words with the same key go in the same list.

Approach 1

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String w : strs) {
            char[] cs = w.toCharArray();
            Arrays.sort(cs);
            groups.computeIfAbsent(new String(cs), k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(groups.values());
    }
}

Verdict: Clear and usually fast enough.

Optimal: letter counts as the key

Time O(n · k) Space O(n · k)

Count the 26 letters of each word and turn the counts into a string key. Building the key is O(k), so there's no sorting.

Approach 2

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String w : strs) {
            int[] count = new int[26];
            for (char c : w.toCharArray()) count[c - 'a']++;
            StringBuilder key = new StringBuilder();
            for (int c : count) key.append(c).append('#');   // '#' keeps "1,11" and "11,1" apart
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(groups.values());
    }
}

Verdict: Linear in the total input size.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty string
All words anagrams of each other
No two words anagrams

Mistakes people make

Building the count key without separators, so different count arrays can produce the same string.
Using the char[] itself as the key (identity equality).

Interview

Follow-up questions

Why does the separator matter in the count key?

Command Palette