# Counting and Canonical Keys — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/h-count

> Group things that are "the same".

## 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.

```python
# 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.

**Quiz:** What makes a good key for grouping anagrams?

- [ ] A random number
- [ ] The word length only
- [ ] The first letter
- [x] The sorted letters of each word

*Answer:* The sorted letters of each word. Equivalent items share a key.