# Group Anagrams

[link](https://leetcode.com/problems/group-anagrams/) · Medium · `array`, `hash map`, `string`, `sorting`

> "group things that are equivalent" → compute a canonical key for each item and group with defaultdict(list) (key → items). For anagrams the key is the sorted word or the 26-count tuple.

## Problem

> Given an array of strings `strs`, group all anagrams together into sublists.
> You may return the output in any order. An anagram is a string that contains the
> exact same characters as another string, in any order.

**Example 1**
```
Input:  strs = ["act", "pots", "tops", "cat", "stop", "hat"]
Output: [["hat"], ["act", "cat"], ["stop", "pots", "tops"]]
```

**Example 2**
```
Input:  strs = ["x"]
Output: [["x"]]
```

**Example 3**
```
Input:  strs = [""]
Output: [[""]]
```

**Constraints**
- `1 <= len(strs) <= 10^4`
- `0 <= len(strs[i]) <= 100`
- `strs[i]` is made up of lowercase English letters.

## Thinking

Let $m$ = number of strings, $k$ = max string length.

- **Brute force idea:** compare every pair of strings with an anagram check → $O(m^2 \cdot k)$.
- **Key insight:** give every word a **key that is the same for all its anagrams and different
  for everything else**, then group with a dict of *key → list of words*. Two keys work:
  - the sorted word (`"tops"` → `"opst"`): $O(k \log k)$ per word;
  - the 26 letter counts as a **tuple**: $O(k)$ per word (see Valid Anagram #242).
- **The key must be unambiguous:** two different count lists must never produce the same key.
- **Edge cases to remember:** empty string `""`, single word, one letter repeated 10+ times
  (two-digit counts), words that are all anagrams / none are.

## Solution

### Approach A — my first version (has two bugs)
The counting idea is right, but:
1. **Wrong output shape:** `seen.values()` already holds lists, so `[words]` wraps each group in
   one more list → `[[["act", "cat"]], ...]`.
2. **Key collision:** joining the counts with no separator loses where one count ends and the next
   begins. 1 `a` + 11 `b` → counts `1, 11, 0, …` → `"111000…"`; 11 `a` + 1 `b` → `11, 1, 0, …`
   → also `"111000…"`. Different words, same key, wrongly grouped. It only happens when a letter
   appears 10+ times, so all three examples pass.

Kept here unchanged so the bugs can be demonstrated (see Tests).

```python
from collections import defaultdict

def group_anagrams_v1(strs: list[str]) -> list[list[str]]:
    seen = defaultdict(list)
    for word in strs:
        key = [0] * 26
        for char in word:
            key[ord(char) - ord("a")] += 1
        seen["".join(str(i) for i in key)].append(word)  # BUG 2: "1"+"11" == "11"+"1"
    result = [[words] for words in seen.values()]        # BUG 1: words is already a list
    return result
```

### Approach B — my fixed version: letter counts as a tuple key ✅ best practice
A tuple keeps each count as a separate element, so `(1, 11, 0, …)` and `(11, 1, 0, …)` are
different keys. Tuples are hashable (immutable), lists are not, so a tuple can be a dict key.

**Complexity:** Time $O(m \cdot k)$ · Space $O(m \cdot k)$ for the output (each key is a fixed 26 ints).

```python
def group_anagrams(strs: list[str]) -> list[list[str]]:
    seen = defaultdict(list)
    for word in strs:
        key = [0] * 26
        for char in word:
            key[ord(char) - ord("a")] += 1
        seen[tuple(key)].append(word)
    return list(seen.values())
```

### Approach C — sorted word as key (Hint 1's "naive" solution)
All anagrams sort to the same string, and the letters themselves are the key, so it can't collide.

**Complexity:** Time $O(m \cdot k \log k)$ · Space $O(m \cdot k)$. Simplest to write, and often faster
in Python in practice (see Scratch).

```python
def group_anagrams_sorted(strs: list[str]) -> list[list[str]]:
    seen = defaultdict(list)
    for word in strs:
        seen["".join(sorted(word))].append(word)
    return list(seen.values())
```

## Scratch / Experiments

Worst case at the max size: $10^4$ random words of 100 letters.

Big-O says counting ($O(k)$ per word) beats sorting ($O(k \log k)$), but in Python the counting
loop runs character by character in Python bytecode, while `sorted` and `"".join` run in C.
With $k \le 100$, $\log k$ is tiny, so sorting usually wins on the clock. In an interview, explain
the counting key; in everyday Python, the sorted key is fine.

```python
import random, string

words = ["".join(random.choices(string.ascii_lowercase, k=100)) for _ in range(10_000)]
%timeit group_anagrams(words)
%timeit group_anagrams_sorted(words)
```

## Takeaways

- **Pattern:** "group things that are equivalent" → compute a **canonical key** for each item and
  group with `defaultdict(list)` (key → items). For anagrams the key is the sorted word or the
  26-count tuple.
- **Mistakes I made:**
  - Built a string key by gluing numbers together with no separator → different count lists
    produced the same key. When you combine several values into one key, use a **tuple**
    (or add a separator like `","`). The bug only shows up with two-digit counts, so test with a
    letter repeated 10+ times.
  - Wrapped each group in an extra list. `seen.values()` already gives the groups:
    `return list(seen.values())`.
  - Lists can't be dict keys (unhashable, because they can change); tuples can.
- **Related problems:** Valid Anagram (#242, same counting idea for two strings), Find All Anagrams
  in a String (#438, counts + sliding window), Group Shifted Strings (#249, a different canonical key),
  Top K Frequent Elements (#347, dict of counts).

---

From https://taosu.blog/notes/0049-group-anagrams