Group anagrams: bucket words that share the same letters

Given a list of words, group the words that are anagrams of one another (the same letters, each the same number of times). Every input word appears in exactly one group, and repeated words stay repeated. Build each word's grouping key from its letter counts, not by sorting its letters.

Interface

Unless you agree on a different interface with the interviewer, assume:

• group_anagrams(words: list[str]) -> list[list[str]] — groups ordered by the first appearance of any member; words inside a group keep their input order.

Example

group_anagrams(["eat", "tea", "bat", "ate", "bat"])  ->  [["eat", "tea", "ate"], ["bat", "bat"]]
group_anagrams(["ab", "cd", "ba", "dc", "ab"])       ->  [["ab", "ba", "ab"], ["cd", "dc"]]
group_anagrams(["", ""])                             ->  [["", ""]]
group_anagrams([])                                   ->  []

Constraints

• Words are lowercase a–z; up to 10^4 words of up to 100 letters.

Clarifying questions

• Only lowercase letters, or any characters?
• Do duplicates stay as separate entries?
• Does the order of groups or of words inside a group matter?

What a strong answer covers

• A 26-count tuple per word as the dictionary key: O(L) per word instead of O(L log L) for sorting.
• A dictionary that remembers insertion order (or a separate list of keys) for the output order.
• O(total letters) time and space.
• Why a product-of-primes key is risky: it overflows fixed-width integers, and big-integer products are slow.

Follow-ups

• Unicode words: what key do you use then?
• Words arrive as a stream and each must be placed as it comes.
• Find the largest anagram group across a file too big for memory.