Group Anagrams: Categorizing by Character Counts
The Prompt
Given an array of strings `strs`, group the anagrams together. You can return the answer in any order.
Understanding the Problem
You must partition a list of strings into clusters where every pair inside a cluster is an anagram pair. Comparing strings pairwise is O(n²) comparisons — and each comparison itself costs work. The bottleneck is that "is an anagram of" is a relationship between two strings, which seems to force pair checks.
The escape is to turn the relationship into a property of a single string: a canonical form. If two strings sort to the same character sequence, they are anagrams — "eat", "tea", and "ate" all sort to "aet". Now grouping is just bucketing by that canonical key in a hash map, one string at a time.
The Interview Flow
Interviewer
Given an array of strings, how would you group the anagrams together?
Candidate
Anagrams are words with the same characters, just rearranged. This means that if I sort the characters of two strings that are anagrams, the sorted versions will be identical.
Interviewer
That's a key insight. How would you use that to solve the problem?
Candidate
I could use a hash map where the key is the sorted version of a string, and the value is a list of all strings from the input that match this sorted key. I would iterate through the input array, sort each string, and use it as a key to append the original string to the corresponding list in my map.
Interviewer
What would the final result be?
Candidate
After iterating through all the strings, the values of the hash map would be the groups of anagrams. I can just return all the values from the map as the final result.
Interviewer
That approach sounds correct and efficient. What about an alternative to sorting each string?
Candidate
Instead of sorting, I could create a character frequency count for each string. For example, a tuple or a string representation of a 26-element array (for lowercase English letters). This count would be the unique key for each anagram group. This avoids the O(k log k) sorting cost for each string of length k.
Interviewer
Both are great solutions. Let's proceed with the sorting approach for implementation.
Why does sorting each string as a key work?
Sorting is a canonicalizer: it maps every member of an anagram family to the same representative and maps non-anagrams to different ones (different letter counts must produce different sorted strings). So the map invariant holds throughout the scan — each bucket contains exactly the strings sharing one canonical form — and no string ever needs to be compared with another directly.
Cost: n strings of length up to k gives O(n · k log k) time for the sorts and O(n · k) space for the map. If the interviewer pushes for better, swap the sorted key for a 26-slot count signature — building it is O(k), dropping the total to O(n · k). Either way you pay memory for the map to avoid quadratic pair comparisons.
Solution using a Hash Map and Sorted Keys
- Initialize an empty hash map, say `anagram_groups`.
- Iterate through each string in the input array `strs`.
- For each string, create a key by sorting its characters. For example, "eat" becomes "aet".
- Check if this sorted key exists in `anagram_groups`.
- If the key exists, append the original string to the list of strings associated with that key.
- If the key does not exist, create a new entry in the map with the sorted key and a new list containing the original string.
- After iterating through all strings, the values of the `anagram_groups` map will be the required groups. Return these values.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function groupAnagrams(strs) {
const map = new Map();
for (const str of strs) {
const sortedStr = str.split('').sort().join('');
if (!map.has(sortedStr)) {
map.set(sortedStr, []);
}
map.get(sortedStr).push(str);
}
return Array.from(map.values());
}Explanation
Bucket strs = ["eat", "tea", "tan", "ate", "nat", "bat"] by sorted key.
1i = 0: sort "eat" → key "aet". No such bucket yet, so create one: {aet: [eat]}.
2i = 1: "tea" also sorts to "aet" — append to the existing bucket. i = 2: "tan" sorts to "ant", a new bucket. Map: {aet: [eat, tea], ant: [tan]}.
3i = 3..5: "ate" → "aet" (highlighted family complete), "nat" → "ant", "bat" → "abt". Buckets: [eat, tea, ate], [tan, nat], [bat] — return the map values.
Complexity Analysis
TIME
O(n * k log k)
SPACE
O(n * k)
Finished working through this one?
Mark it complete to track it on your Data Structures path.