Group anagrams: canonical keys

Replace pairwise questions with a shared identity

A baseline compares each word with a representative of every existing group using the previous anagram checker. In the worst case, each word starts a new group, giving O(w² L) work for w words of maximum length L. The useful question is no longer “Are these two equal?” but “Can all equivalent words compute the same key independently?” A canonical key represents an entire equivalence class: equality of keys must hold exactly when the words are anagrams, not merely often.

Sorting the characters supplies such a key: equal inventories sort identically, and identical sorted strings contain identical counts. After processing a prefix, the map has one group for each key seen, with members in original order. Python dictionaries preserve insertion order, so the map also preserves first-group order. Append to an existing group or create one at first sight; both transitions preserve the invariant. Avoid a set of words, which would destroy multiplicity.

Let T be total characters and w the number of words. The reference costs O(w + Σ length(word) log(max(2, length(word)))) expected time. Key storage costs O(T) auxiliary space in the worst case; group bookkeeping adds O(w), including references in the output. Excluding returned groups, retained keys and the map still cost O(T + w) worst case. No word contents are copied into the output.

Follow-up 1: alphabet is exactly lowercase English

Predict a cheaper key when the contract restricts all characters to a–z. Count into 26 slots and use a tuple, not a concatenated decimal string whose field boundaries might be ambiguous.

The new bound is O(T + 26w) time and O(26g) key space for g groups. Validate the alphabet; applying this array to arbitrary Unicode breaks the original API.

Follow-up 2: workers group separate partitions

Independent local grouping is insufficient if equivalent words land on different workers. Redraw the data flow before selecting a transport:

Global ordering needs original positions; worker arrival order does not preserve the contract. A senior candidate defends collision-free key semantics and counts output storage. A lead candidate defines one key-encoding version across workers, handles a single enormous group, and separates partitioning hashes from exact key equality. Hash collisions may co-locate keys but must never merge groups.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/03-group-anagrams
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def group_anagrams(words):
    if not isinstance(words, (list, tuple)) or any(not isinstance(word, str) for word in words):
        raise ValueError("expected a list or tuple of strings")
    groups = {}
    for word in words:
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    return list(groups.values())

import random
import unittest
from collections import Counter
from solution import group_anagrams

class GroupTests(unittest.TestCase):
    def test_contract(self):
        self.assertEqual(group_anagrams(["eat", "tea", "tan", "eat", "ate"]),
                         [["eat", "tea", "eat", "ate"], ["tan"]])
        self.assertEqual(group_anagrams([]), [])
        self.assertEqual(group_anagrams(["", ""]), [["", ""]])
        self.assertEqual(group_anagrams(["é", "e\u0301", "é"]), [["é", "é"], ["e\u0301"]])
        with self.assertRaises(ValueError):
            group_anagrams(["ok", 7])

    def test_pairwise_inventory_oracle(self):
        rng = random.Random(103)
        for _ in range(200):
            words = ["".join(rng.choices("abc", k=rng.randrange(6)))
                     for _ in range(rng.randrange(20))]
            expected = []
            for word in words:
                for group in expected:
                    if Counter(word) == Counter(group[0]):
                        group.append(word)
                        break
                else:
                    expected.append([word])
            original = words[:]
            self.assertEqual(group_anagrams(words), expected)
            self.assertEqual(words, original)

if __name__ == "__main__":
    unittest.main()