Group Anagrams
Given a list of lowercase words, group together all words that are anagrams of each other (the same multiset of letters). Return the groups in any order.
- 1 ≤ strs.length ≤ 10^4
- 0 ≤ strs[i].length ≤ 100
- Only lowercase English letters
- Words in the same group share an identical *canonical form*
- Need to bucket items by a computed key
- Only 26 possible letters — a fixed-size count works as a key
Whenever a brute force re-scans earlier elements to check membership, count, or a complement, a hash table answers the same question in expected O(1) and turns O(n^2) into O(n). Grouping problems reduce to choosing a canonical key (a sorted string, a character-count tuple) and bucketing by it.
Map each word to a canonical key that is identical for all its anagrams: either the sorted word or a 26-entry letter count serialized to a string. Insert every word into a hash map keyed by that form. The map values are exactly the groups. Using letter counts keeps the key cost linear in word length instead of O(L log L).
- Sorting each word as the key is simpler to write and costs O(n · L log L); it is the usual interview answer unless L is large.