49. Group Anagrams
You are given strs, an array of lowercase words. Two words are anagrams when one can be rearranged into the other — they use exactly the same letters with the same multiplicities, like tea and ate. Partition strs into groups of mutual anagrams and return the groups.
The output order is pinned so it is deterministic: groups appear in the order their first member appears in strs, and within a group the words keep their input order (duplicated words stay duplicated — every position in strs lands in exactly one group).
The crux is choosing a canonical key per word so that all anagrams collide and nothing else does.
Example 1:
Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
Explanation: eat/tea/ate share the letters {a,e,t}, tan/nat share {a,n,t}, and bat stands alone. The eat-group prints first because eat appears first in the input.
Example 2:
Input: strs = ["ab", "ba", "abc", "cab"]
Output: [["ab","ba"], ["abc","cab"]]
Explanation: ab and ba are anagrams of each other; abc and cab are anagrams of each other. Length alone already separates the two groups.
Constraints:
- 1 ≤ strs.length ≤ 1000
- 1 ≤ strs[i].length ≤ 20
- strs[i] consists of lowercase English letters only.
Hints:
Checking every pair of words for the anagram property is O(n²) comparisons. Instead, compute something per word that is identical for anagrams and different otherwise.
Sorting a word's letters gives such a canonical key: sorted("tea") = sorted("ate") = "aet". Bucket words by that key in a hash map.
You can drop the log factor: a word's 26-letter count vector is also a canonical key, computable in O(k) per word. Turn the counts into a hashable key (tuple, or a delimited string).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Expected output: [["eat","tea","ate"], ["tan","nat"], ["bat"]]