Group Anagrams#

Given a list of strings, group together the ones that are anagrams of each other. Words belong to the same group when they share the same letters with the same counts. Return the groups in any order.

Example#

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Brute force#

Compare every string against every group’s representative by checking if they are anagrams (for example by sorting each). This scales poorly because each new word may be compared with many existing groups.

• Time: O(n^2 * k log k) in the worst case.
• Space: O(n * k).

Optimal approach#

Give every word a canonical key that is identical for all its anagrams, then bucket words by that key in a hash map. Two common keys work: the sorted characters of the word, or a 26-length count of each letter turned into a tuple. Words that hash to the same key are anagrams, so grouping is a single pass.

Python solution#

1from collections import defaultdict
2
3
4def group_anagrams(strs):
5    groups = defaultdict(list)
6    for word in strs:
7        key = tuple(sorted(word))
8        groups[key].append(word)
9    return list(groups.values())

Complexity#

• Time: O(n * k log k), where n is the number of words and k is the max word length (sorting each word). Using a count-based key drops this to O(n * k).
• Space: O(n * k) for the grouped output.

This problem extends the hashing pattern to grouping by a canonical key. Keep going with the 60-day challenge.