{ "cells": [ { "cell_type": "markdown", "id": "7ad964e33812", "metadata": {}, "source": [ "# Group Anagrams\n", "\n", "| Field | Value |\n", "|------------|-----------------------------------------|\n", "| Source | [link](https://leetcode.com/problems/group-anagrams/) |\n", "| Difficulty | Medium |\n", "| Topics | `array`, `hash map`, `string`, `sorting` |\n", "| Date | 2026-10-07 |\n", "| Status | Solved |" ] }, { "cell_type": "markdown", "id": "e329209f826e", "metadata": {}, "source": [ "## 1. Problem\n", "\n", "> Given an array of strings `strs`, group all anagrams together into sublists.\n", "> You may return the output in any order. An anagram is a string that contains the\n", "> exact same characters as another string, in any order.\n", "\n", "**Example 1**\n", "```\n", "Input: strs = [\"act\", \"pots\", \"tops\", \"cat\", \"stop\", \"hat\"]\n", "Output: [[\"hat\"], [\"act\", \"cat\"], [\"stop\", \"pots\", \"tops\"]]\n", "```\n", "\n", "**Example 2**\n", "```\n", "Input: strs = [\"x\"]\n", "Output: [[\"x\"]]\n", "```\n", "\n", "**Example 3**\n", "```\n", "Input: strs = [\"\"]\n", "Output: [[\"\"]]\n", "```\n", "\n", "**Constraints**\n", "- `1 <= len(strs) <= 10^4`\n", "- `0 <= len(strs[i]) <= 100`\n", "- `strs[i]` is made up of lowercase English letters." ] }, { "cell_type": "markdown", "id": "706e6ede4adf", "metadata": {}, "source": [ "## 2. Thinking\n", "\n", "Let $m$ = number of strings, $k$ = max string length.\n", "\n", "- **Brute force idea:** compare every pair of strings with an anagram check → $O(m^2 \\cdot k)$.\n", "- **Key insight:** give every word a **key that is the same for all its anagrams and different\n", " for everything else**, then group with a dict of *key → list of words*. Two keys work:\n", " - the sorted word (`\"tops\"` → `\"opst\"`): $O(k \\log k)$ per word;\n", " - the 26 letter counts as a **tuple**: $O(k)$ per word (see Valid Anagram #242).\n", "- **The key must be unambiguous:** two different count lists must never produce the same key.\n", "- **Edge cases to remember:** empty string `\"\"`, single word, one letter repeated 10+ times\n", " (two-digit counts), words that are all anagrams / none are." ] }, { "cell_type": "code", "id": "0ad0f9ffef4e", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "# Setup: run this cell first. Lets you run pytest tests inside the notebook.\n", "try:\n", " import ipytest\n", "except ImportError: # Colab and other fresh kernels don't ship ipytest\n", " %pip install -q ipytest\n", " import ipytest\n", "import pytest\n", "\n", "ipytest.autoconfig()" ] }, { "cell_type": "markdown", "id": "84daca7ce92e", "metadata": {}, "source": [ "## 3. Solution\n", "\n", "### Approach A — my first version (has two bugs)\n", "The counting idea is right, but:\n", "1. **Wrong output shape:** `seen.values()` already holds lists, so `[words]` wraps each group in\n", " one more list → `[[[\"act\", \"cat\"]], ...]`.\n", "2. **Key collision:** joining the counts with no separator loses where one count ends and the next\n", " begins. 1 `a` + 11 `b` → counts `1, 11, 0, …` → `\"111000…\"`; 11 `a` + 1 `b` → `11, 1, 0, …`\n", " → also `\"111000…\"`. Different words, same key, wrongly grouped. It only happens when a letter\n", " appears 10+ times, so all three examples pass.\n", "\n", "Kept here unchanged so the bugs can be demonstrated (see Tests)." ] }, { "cell_type": "code", "id": "8467ff4eab4a", "metadata": {}, "source": [ "from collections import defaultdict\n", "\n", "def group_anagrams_v1(strs: list[str]) -> list[list[str]]:\n", " seen = defaultdict(list)\n", " for word in strs:\n", " key = [0] * 26\n", " for char in word:\n", " key[ord(char) - ord(\"a\")] += 1\n", " seen[\"\".join(str(i) for i in key)].append(word) # BUG 2: \"1\"+\"11\" == \"11\"+\"1\"\n", " result = [[words] for words in seen.values()] # BUG 1: words is already a list\n", " return result" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "5f7a3ad64a92", "metadata": {}, "source": [ "### Approach B — my fixed version: letter counts as a tuple key ✅ best practice\n", "A tuple keeps each count as a separate element, so `(1, 11, 0, …)` and `(11, 1, 0, …)` are\n", "different keys. Tuples are hashable (immutable), lists are not, so a tuple can be a dict key.\n", "\n", "**Complexity:** Time $O(m \\cdot k)$ · Space $O(m \\cdot k)$ for the output (each key is a fixed 26 ints)." ] }, { "cell_type": "code", "id": "0a92056d9bc6", "metadata": {}, "source": [ "def group_anagrams(strs: list[str]) -> list[list[str]]:\n", " seen = defaultdict(list)\n", " for word in strs:\n", " key = [0] * 26\n", " for char in word:\n", " key[ord(char) - ord(\"a\")] += 1\n", " seen[tuple(key)].append(word)\n", " return list(seen.values())" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "006874bc1bcd", "metadata": {}, "source": [ "### Approach C — sorted word as key (Hint 1's \"naive\" solution)\n", "All anagrams sort to the same string, and the letters themselves are the key, so it can't collide.\n", "\n", "**Complexity:** Time $O(m \\cdot k \\log k)$ · Space $O(m \\cdot k)$. Simplest to write, and often faster\n", "in Python in practice (see Scratch)." ] }, { "cell_type": "code", "id": "d0eb9c360a5b", "metadata": {}, "source": [ "def group_anagrams_sorted(strs: list[str]) -> list[list[str]]:\n", " seen = defaultdict(list)\n", " for word in strs:\n", " seen[\"\".join(sorted(word))].append(word)\n", " return list(seen.values())" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "d4108affacb7", "metadata": {}, "source": [ "## 4. Tests\n", "\n", "The output order doesn't matter (neither the groups nor the words inside a group), so `normalize`\n", "sorts both before comparing. Approaches B and C run against every case.\n", "`test_v1_bugs` checks that both bugs in my first version really happen." ] }, { "cell_type": "code", "id": "ebcf32bbe250", "metadata": {}, "source": [ "%%ipytest -q\n", "\n", "def normalize(groups):\n", " return sorted(sorted(g) for g in groups)\n", "\n", "COLLIDE = [\"a\" + \"b\" * 11, \"a\" * 11 + \"b\"] # 1 a + 11 b vs 11 a + 1 b\n", "\n", "CASES = [\n", " ([\"act\", \"pots\", \"tops\", \"cat\", \"stop\", \"hat\"], [[\"hat\"], [\"act\", \"cat\"], [\"stop\", \"pots\", \"tops\"]]),\n", " ([\"x\"], [[\"x\"]]),\n", " ([\"\"], [[\"\"]]),\n", " ([\"\", \"\", \"a\"], [[\"\", \"\"], [\"a\"]]), # empty strings group together\n", " ([\"abc\", \"bca\", \"cab\"], [[\"abc\", \"bca\", \"cab\"]]), # all anagrams\n", " ([\"ab\", \"cd\", \"ef\"], [[\"ab\"], [\"cd\"], [\"ef\"]]), # no anagrams\n", " ([\"aab\", \"abb\"], [[\"aab\"], [\"abb\"]]), # same letters, different counts\n", " (COLLIDE, [[COLLIDE[0]], [COLLIDE[1]]]), # two-digit counts: v1's string key collides\n", "]\n", "\n", "@pytest.mark.parametrize(\"fn\", [group_anagrams, group_anagrams_sorted])\n", "@pytest.mark.parametrize(\"strs, expected\", CASES)\n", "def test_group_anagrams(fn, strs, expected):\n", " assert normalize(fn(strs)) == normalize(expected)\n", "\n", "def test_v1_bugs():\n", " # Bug 1: every group is wrapped in an extra list\n", " assert group_anagrams_v1([\"x\"]) == [[[\"x\"]]]\n", " # Bug 2: two non-anagrams land in the same group\n", " assert group_anagrams_v1(COLLIDE) == [[COLLIDE]]" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "0817fb3577dd", "metadata": {}, "source": [ "## 5. Scratch / Experiments\n", "\n", "Worst case at the max size: $10^4$ random words of 100 letters.\n", "\n", "Big-O says counting ($O(k)$ per word) beats sorting ($O(k \\log k)$), but in Python the counting\n", "loop runs character by character in Python bytecode, while `sorted` and `\"\".join` run in C.\n", "With $k \\le 100$, $\\log k$ is tiny, so sorting usually wins on the clock. In an interview, explain\n", "the counting key; in everyday Python, the sorted key is fine." ] }, { "cell_type": "code", "id": "433a7a4f03be", "metadata": {}, "source": [ "import random, string\n", "\n", "words = [\"\".join(random.choices(string.ascii_lowercase, k=100)) for _ in range(10_000)]\n", "%timeit group_anagrams(words)\n", "%timeit group_anagrams_sorted(words)" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "cb9d0c3f03b6", "metadata": {}, "source": [ "## 6. Takeaways\n", "\n", "- **Pattern:** \"group things that are equivalent\" → compute a **canonical key** for each item and\n", " group with `defaultdict(list)` (key → items). For anagrams the key is the sorted word or the\n", " 26-count tuple.\n", "- **Mistakes I made:**\n", " - Built a string key by gluing numbers together with no separator → different count lists\n", " produced the same key. When you combine several values into one key, use a **tuple**\n", " (or add a separator like `\",\"`). The bug only shows up with two-digit counts, so test with a\n", " letter repeated 10+ times.\n", " - Wrapped each group in an extra list. `seen.values()` already gives the groups:\n", " `return list(seen.values())`.\n", " - Lists can't be dict keys (unhashable, because they can change); tuples can.\n", "- **Related problems:** Valid Anagram (#242, same counting idea for two strings), Find All Anagrams\n", " in a String (#438, counts + sliding window), Group Shifted Strings (#249, a different canonical key),\n", " Top K Frequent Elements (#347, dict of counts)." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }