Group Anagrams

You'll give every anagram the same hash map key, so each group is one lookup away. You need dictionaries, strings, and sorting. Related chapter: hash maps.

1. The problem

You get a list of lowercase English words. Group the words that use exactly the same letters, each the same number of times. Return all the groups, in any order. Keep duplicate words. This is Group Anagrams (LC 49).

LeetCode never passes an empty list. Our function returns [] for one anyway.

2. A correct baseline

For each word, compare its letter counts with the first word of every group so far.

from collections import Counter

def baseline(words):
    groups = []
    for word in words:
        counts = Counter(word)
        for group in groups:
            if counts == Counter(group[0]):
                group.append(word)
                break
        else:  # Python's for/else runs when the loop did not break.
            groups.append([word])
    return groups

assert baseline(["eat", "tea", "bat"]) == [["eat", "tea"], ["bat"]]
assert baseline(["aab", "abb"]) == [["aab"], ["abb"]]
assert baseline(["", ""]) == [["", ""]]
assert baseline([]) == []

For n words of up to k letters, this takes O(n²k) time in the worst case. When no two words match, every word is compared with every group. On 10,000 words, that's about fifty million comparisons of letter counts.

The bottleneck. Each new word searches the groups one by one, and recounts each group's first word every time.

3. The observation

Sort the letters of eat, tea, and ate, and all three become aet. In general, two words sort to the same string exactly when their letter counts match. So the sorted letters make a hash map key, and each word finds its group in one lookup.

The key has to keep the counts. A set of letters would not: aab and abb would wrongly share the key {a, b}.

4. The solution and a trace

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        """Group lowercase words by letter counts; preserve duplicates."""
        groups = {}  # Sorted letters -> all matching words seen so far.
        for word in strs:
            key = "".join(sorted(word))
            if key not in groups:
                groups[key] = []
            groups[key].append(word)
        return list(groups.values())

solve = Solution().groupAnagrams
assert solve(["eat", "tea", "bat"]) == [["eat", "tea"], ["bat"]]
assert solve(["aab", "abb"]) == [["aab"], ["abb"]]
assert solve(["", ""]) == [["", ""]]
assert solve([]) == []

sorted(word) returns a list of letters. A list can't be a dictionary key, so "".join(...) turns it into a string.

5. Why it works

What stays true. After each step, every word so far sits once in the group for its sorted letters.

No group mixes non-anagrams. Words with the same key have the same letter counts.

No anagrams get split up. Anagrams always sort to the same key. And each word is appended once per time it appears, so duplicates stay.

6. Cost, edge cases, and failure

Cost. Sorting a word of length m takes O(m log m) time, and the lookup is O(1) on average. So the total is the sum of m log m over all words. For n words of up to k letters, that's O(n k log k), with no comparisons between words. The keys take space up to the total number of letters. The output reuses the input strings instead of copying them.

Edge cases. An empty word sorts to the empty key, so empty words group together.

Where it fails. Don't use a set as the key, because a set ignores how often each letter appears:

assert set("aab") == set("abb")  # A set-based key would incorrectly merge them.
assert "".join(sorted("aab")) != "".join(sorted("abb"))

import random
rng = random.Random(49)
normalize = lambda groups: sorted(sorted(group) for group in groups)
for _ in range(1000):
    words = ["".join(rng.choices("abc", k=rng.randrange(7)))
             for _ in range(rng.randrange(15))]
    before = words.copy()
    assert normalize(solve(words)) == normalize(baseline(words))
    assert words == before