DSA Group Anagrams

The problem

Group Anagrams collects words that use the same letters with the same counts. Words with the same letters in a different order belong to one group.

The input is a list of lowercase words. The output is a list of groups. Groups and the words inside each group are printed in sorted order so the answer stays fixed.

cases = [
    (["eat", "tea", "tan", "ate", "nat", "bat"], [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]),
    (["listen", "silent", "enlist"], [["enlist", "listen", "silent"]]),
    (["a"], [["a"]]),
    ([], []),
]
for words, expected in cases:
    print(words, "->", expected)

The first case holds three groups. The word bat stands alone. Its letters match no other word in the list.

Intuition: the first letter does not name a group

A first idea groups words by their opening letter. The idea feels tidy. It fails at once, because anagrams often start with different letters.

words = ["eat", "tea", "ate"]
by_first = {}
for word in words:
    by_first.setdefault(word[0], []).append(word)
for letter in sorted(by_first):
    print(letter, "->", sorted(by_first[letter]))

The three words use the same letters. The first-letter rule still splits them across three groups. A group name must come from all the letters, not the first one.

Brute force: compare every word with every group

The brute force keeps one sample word for each group. A new word is compared with every sample. Two words match when their sorted letters are equal.

A counter records the comparisons. A word that fits no group pays one comparison per group and then starts a new group.

def is_anagram(a, b):
    return sorted(a) == sorted(b)

def group_brute(words):
    groups = []
    samples = []
    compared = 0
    for word in words:
        placed = False
        for i, sample in enumerate(samples):
            compared += 1
            if is_anagram(word, sample):
                groups[i].append(word)
                placed = True
                break
        if not placed:
            samples.append(word)
            groups.append([word])
    result = sorted(sorted(g) for g in groups)
    return result, compared

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
result, compared = group_brute(words)
print("groups:", result)
print("comparisons:", compared)

Six words needed seven sample comparisons here. The count grows as groups multiply. Every comparison also sorts both words again, so the same sorting work repeats.

The optimal solution: build one key per word, then group by key

A key is a value that names a group. Anagrams share one key, and words that are not anagrams get different keys. One dict then gathers each key and its words in a single pass.

The sorted-letters key sorts the letters of a word into one string. The count key counts the 26 lowercase letters into one fixed tuple. Both keys name the same groups.

def group_anagrams(words):
    groups = {}
    for word in words:
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    return sorted(sorted(members) for members in groups.values())

cases = [
    (["eat", "tea", "tan", "ate", "nat", "bat"], [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]),
    (["listen", "silent", "enlist"], [["enlist", "listen", "silent"]]),
    (["a"], [["a"]]),
    ([], []),
]
for words, expected in cases:
    result = group_anagrams(words)
    print(words, "->", result, "match:", result == expected)

def count_key(word):
    counts = [0] * 26
    for ch in word:
        counts[ord(ch) - ord("a")] += 1
    return tuple(counts)

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
groups = {}
steps = 0
for word in words:
    groups.setdefault(count_key(word), []).append(word)
    steps += len(word)
result = sorted(sorted(members) for members in groups.values())
print("groups:", result)
print("letter steps:", steps)

Both keys print the same three groups for the main case. The count key touches each letter once. The sorted key is shorter to write and sorts each word once.

Walkthrough: eat, tea, tan, ate

The walk builds one key per word. The state is the dict from each key to its words so far.

words = ["eat", "tea", "tan", "ate"]
groups = {}
for word in words:
    key = "".join(sorted(word))
    groups.setdefault(key, []).append(word)
    view = {k: groups[k] for k in sorted(groups)}
    print(word, "key", key, "->", view)

The word tea lands under aet with eat. The word tan opens a second key. The word ate joins the first group, and no word ever moves again.

Complexity

The brute force compares each word with up to one sample per group, and each comparison sorts two words, so its time grows with the product of words and groups. The key solution builds one key per word and does one dict step per word after that.

The key solution stores every word once inside its group, so its extra space is O(n) for n words. The brute force stores the same groups plus one sample per group.

for n in [6, 12, 24]:
    pairs = n * (n - 1) // 2
    print("words", n, "- worst pair checks:", pairs, " key builds:", n)

Pair checks grow quadratically. Key builds grow in a straight line. That gap is the whole win.

Edge cases and pitfalls

An empty word sorts to an empty key. Two empty words are anagrams of each other. Repeated copies of one word stay together, because grouping never drops duplicates.

def group_anagrams(words):
    groups = {}
    for word in words:
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    return sorted(sorted(members) for members in groups.values())

print("empty list:", group_anagrams([]))
print("one word:", group_anagrams(["abc"]))
print("empty words:", group_anagrams(["", ""]))
print("repeated word:", group_anagrams(["eat", "eat", "tea"]))
print("different lengths:", group_anagrams(["ab", "aab", "ba"]))

Different lengths can never share a key. The sorted letters of aab carry one more a than the letters of ab. Length is built into the key for free.

Printing groups straight from a dict would follow insertion order. Sorting the groups and their members first keeps the printed answer the same on every run.