Group Anagrams
Asked at Google, Amazon, Apple, Oracle, Adobe, Atlassian, Salesforce, Walmart
Problem
Given an array of strings, group all anagrams together. An anagram is a word formed by rearranging the letters of another word. This problem tests your ability to design a good hash key for grouping.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Amazon | Medium | View all Amazon questions → |
| Apple | Medium | View all Apple questions → |
| Oracle | Medium | View all Oracle questions → |
| Adobe | Medium | View all Adobe questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: compare every pair of strings to check if they're anagrams. That's O(n² × k) where k is string length. Way too slow for large inputs.
Key insight: two strings are anagrams if they produce the same sorted string. "eat" → "aet", "tea" → "aet", "ate" → "aet". Use the sorted string as a hash key. All anagrams map to the same key.
Better approach: instead of sorting (O(k log k)), count character frequencies. For "eat": {a:1, e:1, t:1}. This tuple is the same for all anagrams. O(k) per string instead of O(k log k).
The pattern: create a hash map where key = normalized form (sorted string or frequency tuple), value = list of original strings. Group by key.
Visual walkthrough for ["eat","tea","tan","ate","nat","bat"]:
Sort each: "eat"→"aet", "tea"→"aet", "tan"→"ant", "ate"→"aet", "nat"→"ant", "bat"→"abt"
Map:
"aet" → ["eat", "tea", "ate"]
"ant" → ["tan", "nat"]
"abt" → ["bat"]
Result: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
Edge cases: empty string (group with other empty strings), single character (its own group), strings of different lengths (automatically different keys — can't be anagrams).
Optimal Approach
Approach 1 — Sorted string key:
For each string, sort its characters to get a key. Use a hash map: key → list of original strings. Anagrams produce the same sorted key.
Approach 2 — Frequency tuple key:
Count character frequencies (26 letters). Use the frequency tuple as the hash key. O(k) per string instead of O(k log k).
Visual for ["eat","tea","tan"]:
"eat" → sorted="aet" → map["aet"] = ["eat"]
"tea" → sorted="aet" → map["aet"] = ["eat", "tea"]
"tan" → sorted="ant" → map["ant"] = ["tan"]
Return [["eat","tea"], ["tan"]]
Time: O(n × k log k) for sorting, O(n × k) for frequency. Space: O(n × k) for storing all strings.
What Trips People Up in Real Interviews
Sorting each string to use as the key. This works (sorted anagrams are identical) but is O(k log k) per string where k is the string length. An alternative is a character count tuple as the key, which is O(k).
Forgetting that the problem asks for a list of lists, not a list of strings. Each group is a list, and the result is a list of those lists.
Not handling empty strings. An empty string is an anagram of itself and should be grouped with other empty strings.
Using a sorted string as the key but forgetting to convert it back to a tuple for hashability. In Python, strings are hashable, but if you use a character count, you need a tuple.
Using a frozenset as the hash key instead of a sorted string or frequency tuple. A frozenset loses character counts — "aab" and "abb" produce the same frozenset {a, b} despite being different anagram groups.
Solution Code
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s))
groups[key].append(s)
return list(groups.values())Frequently Asked Questions
What is the Group Anagrams problem?
Given an array of strings, group all anagrams together. An anagram is a word formed by rearranging the letters of another word. This problem tests your ability to design a good hash key for grouping.
How do you solve Group Anagrams?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Group Anagrams?
Group Anagrams is asked at Google, Amazon, Apple, Oracle, Adobe, Atlassian, Salesforce, Walmart. It is a medium difficulty problem.
What are common mistakes on Group Anagrams?
- Sorting each string to use as the key. This works (sorted anagrams are identical) but is `O(k log k)` per string where k is the string length. An alternative is a character count tuple as the key, which is `O(k)`.
- Forgetting that the problem asks for a list of lists, not a list of strings. Each group is a list, and the result is a list of those lists.
- Not handling empty strings. An empty string is an anagram of itself and should be grouped with other empty strings.
- Using a sorted string as the key but forgetting to convert it back to a tuple for hashability. In Python, strings are hashable, but if you use a character count, you need a tuple.
- Using a frozenset as the hash key instead of a sorted string or frequency tuple. A frozenset loses character counts — "aab" and "abb" produce the same frozenset `{a, b}` despite being different anagram groups.