{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "824e22670a73",
   "metadata": {},
   "source": [
    "# Valid Anagram\n",
    "\n",
    "| Field      | Value                                   |\n",
    "|------------|-----------------------------------------|\n",
    "| Source     | [link](https://leetcode.com/problems/valid-anagram/)  |\n",
    "| Difficulty | Easy                    |\n",
    "| Topics     | `string`, `hash map`, `counting`, `sorting`                     |\n",
    "| Date       | 2026-10-07                              |\n",
    "| Status     | Solved           |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd42a7ff0692",
   "metadata": {},
   "source": [
    "## 1. Problem\n",
    "\n",
    "> Given two strings `s` and `t`, return `true` if they are anagrams of each other,\n",
    "> otherwise return `false`. Two strings are anagrams if they contain the same\n",
    "> characters, each appearing the same number of times, in any order.\n",
    "\n",
    "**Example 1**\n",
    "```\n",
    "Input:  s = \"racecar\", t = \"carrace\"\n",
    "Output: true\n",
    "```\n",
    "\n",
    "**Example 2**\n",
    "```\n",
    "Input:  s = \"jar\", t = \"jam\"\n",
    "Output: false\n",
    "```\n",
    "\n",
    "**Example 3**\n",
    "```\n",
    "Input:  s = \"x\", t = \"x\"\n",
    "Output: true\n",
    "```\n",
    "\n",
    "**Constraints**\n",
    "- `1 <= len(s), len(t) <= 5 * 10^4`\n",
    "- `s` and `t` consist of lowercase English letters."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "818c88017ae0",
   "metadata": {},
   "source": [
    "## 2. Thinking\n",
    "\n",
    "- **Brute force idea:** sort both strings and compare → $O(n \\log n)$. Correct, but sorting\n",
    "  does more work than needed: we only care *how many* of each letter, not their order.\n",
    "- **Key insight:** two strings are anagrams ⇔ they have the **same character counts**.\n",
    "  Counting is a single $O(n)$ pass. And since there are only 26 lowercase letters,\n",
    "  the counts fit in a fixed-size array → $O(1)$ extra space.\n",
    "- **Quick reject:** if `len(s) != len(t)`, they can't be anagrams.\n",
    "- **Edge cases to remember:** different lengths, same letters but different counts\n",
    "  (`\"aab\"` vs `\"abb\"`), single character, identical strings."
   ]
  },
  {
   "cell_type": "code",
   "id": "79cf01457371",
   "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": "5d5f8137e2dd",
   "metadata": {},
   "source": [
    "## 3. Solution\n",
    "\n",
    "### Approach A — my first solution (sort and compare)\n",
    "**Complexity:** Time $O(n \\log n)$ · Space $O(n)$ (`sorted` builds a new list of characters)\n",
    "\n",
    "Short and correct. The cost is the sort: it puts every character in order, which is more than\n",
    "the question needs."
   ]
  },
  {
   "cell_type": "code",
   "id": "a18da361ee4b",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def is_anagram_sort(s: str, t: str) -> bool:\n",
    "    return sorted(s) == sorted(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b237ea580bb",
   "metadata": {},
   "source": [
    "### Approach B — `Counter` (Pythonic)\n",
    "`collections.Counter` builds a dict of *character → count*; two Counters are equal when every count matches.\n",
    "\n",
    "**Complexity:** Time $O(n)$ · Space $O(k)$, where $k$ is the number of distinct characters (≤ 26 here).\n",
    "Works for any characters, including Unicode."
   ]
  },
  {
   "cell_type": "code",
   "id": "f9928fe90633",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def is_anagram_counter(s: str, t: str) -> bool:\n",
    "    return Counter(s) == Counter(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "417298760b1a",
   "metadata": {},
   "source": [
    "### Approach C — fixed array of 26 counts ✅ best practice (what interviewers expect)\n",
    "Add 1 for each letter of `s`, subtract 1 for each letter of `t`. They're anagrams if every count ends at 0.\n",
    "`ord(c) - ord('a')` maps `'a'..'z'` to `0..25`.\n",
    "\n",
    "**Complexity:** Time $O(n)$ · Space $O(1)$ (always 26 integers, no matter how long the strings are)."
   ]
  },
  {
   "cell_type": "code",
   "id": "8981e9f7a6f7",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def is_anagram(s: str, t: str) -> bool:\n",
    "    if len(s) != len(t):\n",
    "        return False\n",
    "    count = [0] * 26\n",
    "    for a, b in zip(s, t):\n",
    "        count[ord(a) - ord(\"a\")] += 1\n",
    "        count[ord(b) - ord(\"a\")] -= 1\n",
    "    return all(c == 0 for c in count)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a3f7f9530c3",
   "metadata": {},
   "source": [
    "## 4. Tests\n",
    "\n",
    "All three implementations run against the same cases."
   ]
  },
  {
   "cell_type": "code",
   "id": "32e3860d2faa",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "%%ipytest -q\n",
    "\n",
    "CASES = [\n",
    "    (\"racecar\", \"carrace\", True),\n",
    "    (\"jar\", \"jam\", False),\n",
    "    (\"x\", \"x\", True),\n",
    "    (\"anagram\", \"nagaram\", True),\n",
    "    (\"rat\", \"car\", False),\n",
    "    (\"ab\", \"abc\", False),        # different lengths\n",
    "    (\"aab\", \"abb\", False),       # same letters, different counts\n",
    "    (\"abc\", \"cba\", True),\n",
    "    (\"a\" * 1000 + \"b\", \"b\" + \"a\" * 1000, True),\n",
    "]\n",
    "\n",
    "@pytest.mark.parametrize(\"fn\", [is_anagram_sort, is_anagram_counter, is_anagram])\n",
    "@pytest.mark.parametrize(\"s, t, expected\", CASES)\n",
    "def test_is_anagram(fn, s, t, expected):\n",
    "    assert fn(s, t) == expected"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acdde76957a4",
   "metadata": {},
   "source": [
    "## 5. Scratch / Experiments\n",
    "\n",
    "Timing at the maximum input size ($5 \\cdot 10^4$ characters).\n",
    "\n",
    "Big-O isn't the whole story in Python: `sorted` and `Counter` do their work in C,\n",
    "while Approach C's loop runs in Python, so C can be slower in wall-clock time even though\n",
    "it's the better algorithm. In an interview, C is the answer to explain; in real Python code,\n",
    "`Counter` is the idiomatic choice."
   ]
  },
  {
   "cell_type": "code",
   "id": "8b253bd3b713",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import random, string\n",
    "\n",
    "s = \"\".join(random.choices(string.ascii_lowercase, k=50_000))\n",
    "t = \"\".join(random.sample(s, len(s)))  # a shuffled copy, so it's an anagram\n",
    "%timeit is_anagram_sort(s, t)\n",
    "%timeit is_anagram_counter(s, t)\n",
    "%timeit is_anagram(s, t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52f42cdccd8b",
   "metadata": {},
   "source": [
    "## 6. Takeaways\n",
    "\n",
    "- **Pattern:** \"same elements, any order\" → **compare frequency counts** instead of sorting.\n",
    "  Small fixed alphabet (e.g. 26 lowercase letters) → use an **array of size 26** for $O(1)$ space;\n",
    "  otherwise use a dict / `Counter`.\n",
    "- **Mistakes I made:** reached for sorting, which is $O(n \\log n)$, when counting is $O(n)$.\n",
    "  Also skipped the cheap `len(s) != len(t)` early exit.\n",
    "- **Related problems:** Contains Duplicate (#217, hash set), Group Anagrams (#49, use the sorted\n",
    "  string or a 26-count tuple as a dict key), Find All Anagrams in a String (#438, sliding window +\n",
    "  counts), Ransom Note (#383, counts)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}