Arrays & Hashing · LC #49
Group Anagrams
Group an array of strings by their anagram equivalence class. The key insight is choosing a canonical representation - sorted characters or a frequency-count tuple - that maps all anagrams to the same hash-map key.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an array of strings `strs`, group the **anagrams** together. Return the groups in any order.
Sample I/O
Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]] Input: strs = [""] Output: [[""]]
Intuition
How to Think About It
Intuition
Two strings are anagrams if they produce the same key under any canonical transformation. Sorting the characters is the simplest such transformation: "eat", "tea", and "ate" all sort to "aet". We use that sorted string as a hash-map key to bucket all anagrams together automatically.
Core Concept
For each string in strs, compute its canonical key (sort characters or build a frequency-count tuple). Use the key to look up the group in a hash map and append the original string. After processing all strings, return the map's values. Time: O(n · k log k) for sort-based key where k is max word length; O(n · k) for frequency-tuple key.
When to use
Any problem requiring grouping by character composition: spell-checker grouping, duplicate detection in rotated/shifted strings, deduplication pipelines for natural language data.
When NOT to use
When word order within the group matters - the map does not preserve insertion ordering guarantees across all language runtimes. When k (word length) is extremely large - the sort cost dominates; prefer the O(k) frequency-tuple key.
Key Insights
What to Know Cold
- The sorted-string key is simple to implement; the frequency-tuple key is O(k) instead of O(k log k) - both are correct.
- An empty string "" is its own anagram group (maps to key "" or tuple of all zeros).
- In Java, use Arrays.sort on the char array then new String(chars) to build the key.
- Python's tuple(sorted(s)) is hashable and works directly as a dict key without string conversion.
- This problem is a direct application of "canonical form hashing" - a pattern reused in find-all-anagrams, scramble detection, and isomorphic strings.
1 example
Worked Examples
Sorted-Key Bucketing
strs = ["eat","tea","tan","ate","nat","bat"]. Group all anagrams.
Sort each string: eat→aet, tea→aet, tan→ant, ate→aet, nat→ant, bat→abt. Keys aet, ant, abt map to three groups.
from collections import defaultdict
groups = defaultdict(list)
for s in ["eat","tea","tan","ate","nat","bat"]:
groups[tuple(sorted(s))].append(s)
print(list(groups.values()))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Group Anagrams is a top-3 most-asked Amazon and Google coding screen problem. Nailing the canonical-key pattern here makes Valid Anagram, Find All Anagrams in a String, and Scramble String straightforward.