Counting and Canonical Keys

Counter and normalised keys

collections.Counter counts items and compares frequency profiles (anagrams have equal counters). To group equivalent items, map each to a canonical key: sorted letters for anagrams, a tuple of 26 letter counts for long words (O(k) instead of O(k log k)), or a normalised shape for islands. defaultdict(list) collects groups without key checks.

Grouping anagrams and counting letters, run

I ran this with Python 3.12.3 (standard library only). Words with the same sorted letters share a group; most_common returns the top counts, and equal counters identify anagrams.

# Group anagrams: a canonical key per group
from collections import Counter, defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
print(Counter("mississippi").most_common(2))
print(Counter("listen") == Counter("silent"))

Output:

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[('i', 4), ('s', 4)]
True

Mention the alphabet assumption

A fixed 26-count array is O(1) space only if input is limited to lowercase English letters; say so.

त्वरित जाँच: What makes a good key for grouping anagrams?

• A random number
• The word length only
• The first letter
• The sorted letters of each word