# Group Anagrams

- **Canonical ID**: `group-anagrams`
- **Canonical URL**: https://dsacheatsheet.com/problems/group-anagrams
- **Difficulty**: medium
- **Patterns**: Arrays & Hashing
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/group-anagrams/

## 1. Core Invariant / The Trick

Canonicalize every string to its 26-letter frequency signature (avoiding K log K sorting overhead per string) and bucket strings sharing the identical signature.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N * K)`
- **Space Complexity**: `O(N * K)`
- **Proof**: N strings each of max length K are hashed into a 26-bin frequency tuple in O(K) time.

## 3. Minimal Idiomatic Code

### Python
```python
def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - 97] += 1
        groups[tuple(cnt)].append(s)
    return list(groups.values())
```

### TypeScript
```typescript
export function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const s of strs) {
    const cnt = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - 97]++;
    const key = cnt.join('#');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key)!.push(s);
  }
  return Array.from(groups.values());
}
```

### C++
```cpp
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> m;
    for (auto& s : strs) {
        string k = s;
        sort(k.begin(), k.end());
        m[k].push_back(s);
    }
    vector<vector<string>> res;
    for (auto& [k, v] : m) res.push_back(move(v));
    return res;
}
```

### Java
```java
List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> m = new HashMap<>();
    for (String s : strs) {
        char[] ch = s.toCharArray();
        Arrays.sort(ch);
        m.computeIfAbsent(new String(ch), k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(m.values());
}
```

### Go
```go
func groupAnagrams(strs []string) [][]string {
    m := make(map[[26]int][]string)
    for _, s := range strs {
        var cnt [26]int
        for i := 0; i < len(s); i++ { cnt[s[i]-'a']++ }
        m[cnt] = append(m[cnt], s)
    }
    res := make([][]string, 0, len(m))
    for _, v := range m { res = append(res, v) }
    return res
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Forgetting separator delimiters when serializing counts (`[1, 12]` vs `[11, 2]`).

### Follow-ups
- Large strings: sort or rolling hash vs prime product (watch overflow on prime products).