Group Anagrams

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

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

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

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.

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