Group Anagrams

MediumHash Tables · Canonical Key🧩 Hashing & Counting LeetCode #49 ↗Updated Oct 30, 2026

Problem

You are given an array of lowercase strings strs. Partition them into groups such that two words share a group exactly when one is a rearrangement of the letters of the other. Return the groups; neither the group order nor the order inside a group matters.

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

Input[""]Output[[""]]

Input["a"]Output[["a"]]

1 ≤ n ≤ 10⁴ · 0 ≤ strs[i].length ≤ 100 · lowercase English letters only

Try it yourself

Java

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Give every word a canonical key that is identical for all its anagrams (sorted letters, or the 26 letter counts), then bucket words by key in a hash map.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForcePairwise Anagram Check

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

Take the first unassigned word as a group leader, then scan all later words and pull in every unassigned word that is an anagram of it (checked with a 26-count array in O(k)). A used[] flag stops a word joining twice.

Java

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> res = new ArrayList<>();
    boolean[] used = new boolean[strs.length];
    for (int i = 0; i < strs.length; i++) {
        if (used[i]) continue;
        List<String> group = new ArrayList<>();
        group.add(strs[i]);
        for (int j = i + 1; j < strs.length; j++) {
            if (!used[j] && isAnagram(strs[i], strs[j])) {
                group.add(strs[j]);
                used[j] = true;
            }
        }
        res.add(group);
    }
    return res;
}

private boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;
    int[] cnt = new int[26];
    for (int i = 0; i < a.length(); i++) {
        cnt[a.charAt(i) - 'a']++;
        cnt[b.charAt(i) - 'a']--;
    }
    for (int c : cnt) if (c != 0) return false;
    return true;
}

Correct and simple, but compares up to n²/2 word pairs.

BetterHash Map Keyed by Sorted Word

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

Anagrams become the same string once their letters are sorted ("tea" → "aet"). Use that sorted string as the map key so each word finds its group in one hash lookup instead of n comparisons.

Java

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String word : strs) {
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        groups.computeIfAbsent(key, x -> new ArrayList<>()).add(word);
    }
    return new ArrayList<>(groups.values());
}

One pass over the words; sorting each word costs the extra log k.

OptimalHash Map Keyed by Letter Counts

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

Two words are anagrams iff their 26 letter counts match. Count in O(k) and encode the counts as a string like #1#0#0...; the # separator keeps counts such as 1,11 and 11,1 distinct. No sorting needed.

Java

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String word : strs) {
        int[] count = new int[26];
        for (char c : word.toCharArray()) count[c - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int c : count) sb.append('#').append(c);
        groups.computeIfAbsent(sb.toString(), x -> new ArrayList<>()).add(word);
    }
    return new ArrayList<>(groups.values());
}

Linear in total characters (plus a constant 26 per word for the key).

Pro tip

Use Arrays.toString(count) or a char[26] key as a quick, collision-free alternative to the manual # encoding.

At a glance

Level	Approach	Time	Space
Brute Force	Pairwise Anagram Check	`O(n² · k)`	`O(n · k)`
Better	Hash Map Keyed by Sorted Word	`O(n · k log k)`	`O(n · k)`
Optimal	Hash Map Keyed by Letter Counts	`O(n · k)`	`O(n · k)`

Common pitfalls

Building the count key without separators — different count vectors can collide.
Using int[] directly as a map key — arrays hash by identity, not content.
Dropping the empty string — "" is a valid word and forms its own group.

Interview tips

Frame it as “choose a canonical form”, then compare sort-key vs count-key costs.
Ask whether input is lowercase-only; for Unicode, prefer the sorted key.
Mention computeIfAbsent to keep the grouping code to one line.

Pattern

Canonical key + hash map grouping → bucket items that are equivalent under some transformation.

My notes saved in this browser