Group Anagrams (LC 49)

Pattern: Hashing / Frequency Map Key
Difficulty: Medium
Key Concept: Anagrams share the same character counts—use a canonical key (sorted string or count signature) as the HashMap key.

Problem Statement

Given an array of strings strs, group the anagrams together. You may return the answer in any order.

An anagram is a word formed by rearranging letters of another, using all original letters exactly once.

Input

• strs: String[] — length up to ~10⁴ strings, each up to ~100 chars typical

Output

• List<List<String>> — each inner list is a group of mutual anagrams

Example

• ["eat","tea","tan","ate","nat","bat"] → [["bat"],["nat","tan"],["ate","eat","tea"]] (order may vary)

---

1. Algorithm & Pseudocode

Brute force

For each string, compare character counts to every other string and union into groups — O(n² · L).

groups = []
for each s in strs:
    placed = false
    for group in groups:
        if sameMultiset(s, representative of group):
            add s to group; placed = true; break
    if not placed:
        new group [s]

Optimal

Key A — sort characters: key(s) = sort(s.toCharArray()) — anagrams produce the same key.

Key B — count signature: key = "#1#2#0#...#" for a..z counts — O(L) per string, no sort log factor.

map = HashMap<String, List<String>>
for s in strs:
    k = canonicalKey(s)
    map.computeIfAbsent(k, __ -> new ArrayList<>()).add(s)
return all values in map

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why sorting works Anagrams are permutations; sorting destroys order but preserves multiset—two anagrams become the same string key.

2. Why count signature works Instead of sorting O(L log L), count 26 letters in O(L) and build a fixed pattern string.

3. Why HashMap Groups need dynamic buckets keyed by canonical form; average O(1) insert/lookup.

4. Empty string All empty strings share the same key ("" sorted is "", or all-zero counts).

---

3. The Dry Run

Sample: ["eat", "tea", "tan"].

word	sorted key
eat	aet
tea	aet
tan	ant

Map

aet -> [eat, tea]
ant -> [tan]

ASCII

eat -> sort -> aet  \
tea -> sort -> aet  --> same bucket
tan -> sort -> ant  --> different bucket

---

4. Java Solution

Brute Force

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> groups = new ArrayList<>();
        for (String s : strs) {
            boolean placed = false;
            for (List<String> g : groups) {
                if (sameAnagram(s, g.get(0))) {
                    g.add(s);
                    placed = true;
                    break;
                }
            }
            if (!placed) {
                List<String> g = new ArrayList<>();
                g.add(s);
                groups.add(g);
            }
        }
        return groups;
    }

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

Time: O(n² · L) worst case comparing to group heads.
Space: O(n · L) for stored strings.

Optimal (sorted key)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

Time: O(n · L log L) for sorting keys.
Space: O(n · L).

Optimal (count key)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            int[] cnt = new int[26];
            for (int i = 0; i < s.length(); i++) {
                cnt[s.charAt(i) - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(cnt[i]);
            }
            String key = sb.toString();
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

Time: O(n · L).
Space: O(n · L).

---

5. The “Java vs. Others” Edge

• Arrays.sort(char[]) Sorts UTF-16 code units; assumes lowercase a..z for the count-key version—use a broader table for Unicode problems.
• computeIfAbsent Clean Java 8+ idiom; avoids manual get/put boilerplate.
• Python collections.defaultdict(list) + tuple(count) is the analog of the count-key approach.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (pair to groups)	O(n² · L)	O(n · L)	Compare multiset to group representative.
Hash + sort key	O(n · L log L)	O(n · L)	Simple to code.
Hash + count key	O(n · L)	O(n · L)	Best asymptotic for lowercase alphabet.