49. Group Anagrams
Model: qwen3.5:9b
Topics: Hash Table,String
FAANG asked: 1
Acceptance rate: 59.7%
Problem Breakdown
We are given an array of strings strs. The goal is to group all words that are anagrams into the same sub-list. An anagram means two strings contain exactly the same characters with the exact same frequencies, regardless of order (e.g., “eat” and “tea”).
Inputs: A list of lowercase English letter strings (1 <= strs.length).
Outputs: A 2D array where each inner array contains a group of anagrams. The order of groups or words within groups does not matter.
Constraints & Edge Cases:
- Strings can be empty (length 0). An empty string is its own canonical key
"". If multiple empty strings exist, they share this key and are grouped into the same list in the output. - Input length up to , individual word length up to . This suggests we need better than quadratic time complexity relative to the number of words.
Intuition
A brute-force approach would be to compare every pair of strings in the array to check if they are anagrams (sorting each and comparing, or counting characters). That results in where is the number of words and is string length. With , this will time out.
The key insight for grouping problems like this is finding a canonical representation (a unique identifier) that remains constant regardless of character order.
If we sort the characters in every word, all anagrams will produce the exact same sorted string. For example: "eat", "tea", and "ate" all become "aet".
We can use a Hash Map where the key is this canonical representation (the sorted string) and the value is a list of original words that match it. This reduces us to iterating through the array once, or depending on how we compute the key.
Approach
- Initialize an empty dictionary (hash map).
- Iterate over each string
sin the input liststrs. - Compute a unique key for
s. The most Pythonic way is to sort its characters:key = "".join(sorted(s)). Alternatively, we could use a frequency tuple of counts ‘a’-‘z’, but sorting handles any character set naturally and leverages optimized C internals in Python. - Use the dictionary’s
.get()method or initialize logic to appendsto the list associated with that key. If the key doesn’t exist, create an empty list first. - After processing all strings, return the values of the dictionary as a list of lists.
Complexity Analysis
- Time: where is number of words and is max word length. Sorting each string takes . We do this for every word ( times). Dictionary operations are average .
- Space: to store the output groups plus the dictionary overhead (keys and lists of strings).
Solution
from typing import List
def groupAnagrams(strs: List[str]) -> List[List[str]]:
# Dictionary mapping sorted string key -> list of original anagram words
anagram_map = {}
for word in strs:
# Create a canonical key by sorting characters.
# "eat" -> ['a', 'e', 't'] -> join to "aet". All anagrams share this key.
sorted_key = "".join(sorted(word))
if sorted_key not in anagram_map:
anagram_map[sorted_key] = []
anagram_map[sorted_key].append(word)
# Return the grouped lists as a list of values from our map
return list(anagram_map.values())
# Example usage (uncomment for testing):
# print(groupAnagrams(["eat","tea","tan","ate","nat","bat"]))
Edge Cases Handled
- Empty strings: If
strscontains"", sorting it results in an empty key. The code creates a group[ ""]. This matches Example 2 behavior correctly. Multiple empty strings will share this single key and be grouped together. - Single element input: Loop runs once, map has one entry with length 1 list. Returns correct structure.
- No Anagrams (all unique): Each word generates a unique sorted key. Map contains entries each with size 1. Correctly returns all words in separate groups.
- All same anagram: All generate the same key, map has one entry containing all input strings.