{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9cbd09345278",
   "metadata": {},
   "source": [
    "# Encode and Decode Strings\n",
    "\n",
    "| Field      | Value                                   |\n",
    "|------------|-----------------------------------------|\n",
    "| Source     | [link](https://leetcode.com/problems/encode-and-decode-strings/)  |\n",
    "| Difficulty | Medium                    |\n",
    "| Topics     | `string`, `design`, `length prefix`                     |\n",
    "| Date       | 2026-10-08                              |\n",
    "| Status     | Solved                                  |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "052e35504203",
   "metadata": {},
   "source": [
    "## 1. Problem\n",
    "\n",
    "> Design an algorithm to encode a list of strings to a string. The encoded string is then sent\n",
    "> over the network and is decoded back to the original list of strings.\n",
    "> Implement `encode(strs) -> str` (Machine 1, sender) and `decode(s) -> list[str]`\n",
    "> (Machine 2, receiver) so that `decode(encode(strs)) == strs`.\n",
    "\n",
    "**Example 1**\n",
    "```\n",
    "Input:  strs = [\"Hello\", \"World\"]\n",
    "Output: [\"Hello\", \"World\"]\n",
    "```\n",
    "\n",
    "**Example 2**\n",
    "```\n",
    "Input:  strs = [\"\"]\n",
    "Output: [\"\"]\n",
    "```\n",
    "\n",
    "**Constraints**\n",
    "- `0 <= len(strs) < 100`\n",
    "- `0 <= len(strs[i]) < 200`\n",
    "- `strs[i]` contains any possible characters out of 256 valid ASCII characters."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb62bb5116f9",
   "metadata": {},
   "source": [
    "## 2. Thinking\n",
    "\n",
    "Let $N$ = total number of characters in all strings, $m$ = `len(strs)`.\n",
    "\n",
    "- **Naive idea (wrong):** join with a separator, `\"#\".join(strs)`, and `split(\"#\")`. It breaks\n",
    "  as soon as a word contains the separator (`[\"a#b\"]` → `\"a#b\"` → `[\"a\", \"b\"]`), and the problem\n",
    "  allows **any** character, so no separator is safe on its own. It also can't tell `[]` from `[\"\"]`.\n",
    "- **Key insight:** don't look *inside* the words at all. Write each word's **length** in front of\n",
    "  it: `\"5#Hello5#World\"`. The decoder reads the length, then **jumps** over exactly that many\n",
    "  characters, so it never matters what they are.\n",
    "  - The `#` only marks where the length's digits end (lengths can have up to 3 digits).\n",
    "  - The first `#` after a header's start is always the real separator, because the header is\n",
    "    only digits.\n",
    "- **The decoder needs an index it controls** (`while i < len(s)`), not a `for` loop, because it\n",
    "  must jump a variable distance.\n",
    "- **Edge cases to remember:** `[]` (encodes to `\"\"`), `[\"\"]` (encodes to `\"0#\"`), words that\n",
    "  contain `#` or digits (`\"1#a\"`, `\"5#\"`), multi-digit lengths (≥ 10 chars), any ASCII character\n",
    "  including `\\x00`."
   ]
  },
  {
   "cell_type": "code",
   "id": "f21831fe7506",
   "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": "a315140c487f",
   "metadata": {},
   "source": [
    "## 3. Solution\n",
    "\n",
    "### Approach A — my version (length + `#` prefix)\n",
    "\n",
    "**Complexity:** Time $O(N)$ · Space $O(N)$. Correct, and the same algorithm as the best practice.\n",
    "- `encode` is fine.\n",
    "- In `decode`, `s.find(\"#\", i)` only scans the few header digits, and `i` jumps over the word,\n",
    "  so every character is visited about once.\n",
    "- `if len(s) == 1: return output` is dead code: no input encodes to a 1-character string\n",
    "  (`[]` → `\"\"`, `[\"\"]` → `\"0#\"`, `[\"a\"]` → `\"1#a\"`). It was a patch for an earlier bug.\n",
    "\n",
    "Unchanged except for the signatures; the commented-out first attempt is left out."
   ]
  },
  {
   "cell_type": "code",
   "id": "ea0ad1de5c41",
   "metadata": {},
   "source": [
    "def encode_mine(strs: list[str]) -> str:\n",
    "    output_list = []\n",
    "    for word in strs:\n",
    "        output_list.append(str(len(word)) + \"#\" + word)\n",
    "    return \"\".join(output_list)\n",
    "\n",
    "def decode_mine(s: str) -> list[str]:\n",
    "    output = []\n",
    "    if len(s) == 1:  # dead code: no encoded string has length 1\n",
    "        return output\n",
    "    i = 0\n",
    "    while i < len(s):\n",
    "        deli = s.find(\"#\", i)\n",
    "        length = int(s[i:deli])\n",
    "        output.append(s[deli + 1: deli + 1 + length])\n",
    "        i = deli + length + 1\n",
    "    return output"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "b113caa22939",
   "metadata": {},
   "source": [
    "### Approach B — length + delimiter prefix ✅ best practice\n",
    "\n",
    "**Complexity:** Time $O(N)$ · Space $O(N)$.\n",
    "My version without the special case, with clearer names: `start` is where the word begins, and\n",
    "the next header begins right after the word ends."
   ]
  },
  {
   "cell_type": "code",
   "id": "9e0ade48f0c0",
   "metadata": {},
   "source": [
    "def encode(strs: list[str]) -> str:\n",
    "    return \"\".join(f\"{len(word)}#{word}\" for word in strs)\n",
    "\n",
    "def decode(s: str) -> list[str]:\n",
    "    result = []\n",
    "    i = 0                          # always points at the start of a header\n",
    "    while i < len(s):\n",
    "        j = s.find(\"#\", i)         # end of the length digits\n",
    "        start = j + 1\n",
    "        end = start + int(s[i:j])\n",
    "        result.append(s[start:end])\n",
    "        i = end                    # jump over the word: never read its contents\n",
    "    return result"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "93cbf9f7495e",
   "metadata": {},
   "source": [
    "### Approach C — fixed-width length header (no delimiter)\n",
    "\n",
    "**Complexity:** Time $O(N)$ · Space $O(N)$.\n",
    "If every length is written with the same number of digits, the decoder doesn't need a `#`: it\n",
    "always reads exactly 3 characters. Lengths are `< 200`, so 3 digits always fit. Real network\n",
    "protocols use this idea with a fixed-size binary length (e.g. 4 bytes). The catch: you must know\n",
    "the maximum length in advance; Approach B works for any length."
   ]
  },
  {
   "cell_type": "code",
   "id": "e94a1ccf1a3f",
   "metadata": {},
   "source": [
    "WIDTH = 3  # len(word) < 200 fits in 3 digits\n",
    "\n",
    "def encode_fixed(strs: list[str]) -> str:\n",
    "    return \"\".join(f\"{len(word):0{WIDTH}d}{word}\" for word in strs)  # 5 -> \"005\"\n",
    "\n",
    "def decode_fixed(s: str) -> list[str]:\n",
    "    result = []\n",
    "    i = 0\n",
    "    while i < len(s):\n",
    "        start = i + WIDTH\n",
    "        end = start + int(s[i:start])\n",
    "        result.append(s[start:end])\n",
    "        i = end\n",
    "    return result"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "dc9cf0bfd362",
   "metadata": {},
   "source": [
    "## 4. Tests\n",
    "\n",
    "The only requirement is the round trip `decode(encode(strs)) == strs`, so every encoder/decoder\n",
    "pair is tested on every case. `test_naive_join_breaks` shows why a separator alone isn't enough."
   ]
  },
  {
   "cell_type": "code",
   "id": "1893c3d9cf7a",
   "metadata": {},
   "source": [
    "%%ipytest -q\n",
    "\n",
    "PAIRS = [(encode_mine, decode_mine), (encode, decode), (encode_fixed, decode_fixed)]\n",
    "\n",
    "CASES = [\n",
    "    [\"Hello\", \"World\"],\n",
    "    [\"\"],\n",
    "    [],                              # empty list encodes to \"\"\n",
    "    [\"\", \"\", \"\"],                    # several empty strings\n",
    "    [\"#\"],                           # the delimiter alone\n",
    "    [\"a#b\"],                         # delimiter inside a word\n",
    "    [\"1#a\", \"b\"],                    # a word that looks like a header\n",
    "    [\"#\", \"##\", \"5#\", \"12#ab\"],      # more fake headers\n",
    "    [\"x\" * 150, \"y\"],                # multi-digit length\n",
    "    [\"x\" * 199] * 99,                # max size\n",
    "    [\"\".join(map(chr, range(256)))[:199], \"\\x00\", \" \"],  # any ASCII, incl. \\x00\n",
    "]\n",
    "\n",
    "@pytest.mark.parametrize(\"enc, dec\", PAIRS)\n",
    "@pytest.mark.parametrize(\"strs\", CASES)\n",
    "def test_round_trip(enc, dec, strs):\n",
    "    assert dec(enc(strs)) == strs\n",
    "\n",
    "def test_naive_join_breaks():\n",
    "    assert \"#\".join([\"a#b\"]).split(\"#\") != [\"a#b\"]   # splits inside the word\n",
    "    assert \"#\".join([]).split(\"#\") == [\"\"]           # [] comes back as [\"\"]"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "ae21d462ab23",
   "metadata": {},
   "source": [
    "## 5. Scratch / Experiments\n",
    "\n",
    "Max size: 99 random strings of 199 characters drawn from all 256 ASCII codes. All three are $O(N)$.\n",
    "A and B are about the same (~33 µs). C is ~30% slower here; the likely cost is the nested format\n",
    "spec `{len(word):0{WIDTH}d}`, which is more work per word than `{len(word)}`. The whole round\n",
    "trip is tens of microseconds, so choose by correctness and simplicity, not speed."
   ]
  },
  {
   "cell_type": "code",
   "id": "c93f2f661d38",
   "metadata": {},
   "source": [
    "import random\n",
    "\n",
    "random.seed(0)\n",
    "strs = [\"\".join(chr(random.randrange(256)) for _ in range(199)) for _ in range(99)]\n",
    "\n",
    "for enc, dec in PAIRS:\n",
    "    print(enc.__name__, \"+\", dec.__name__)\n",
    "    %timeit dec(enc(strs))"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "415dc8af3d16",
   "metadata": {},
   "source": [
    "## 6. Takeaways\n",
    "\n",
    "- **Pattern:** to pack variable-length items that can contain *anything* into one string or\n",
    "  byte stream, use **length-prefix framing**: write the length, then the data, and have the reader\n",
    "  **jump** by the length instead of searching for a separator. (HTTP `Content-Length`, Redis\n",
    "  RESP and protobuf all work this way.) A separator alone only works if you also escape it.\n",
    "- **Mistakes I made:**\n",
    "  - `char.isnumeric` without `()`: that's the method object, which is always truthy.\n",
    "    Methods need `()` to run.\n",
    "  - Read the length as a single character: lengths can have several digits. Read up to the `#`.\n",
    "  - Scanned every character with `for … enumerate(s)`: the loop stopped at `#`s inside words.\n",
    "    **You can't change a `for` loop's index**; assigning to it is overwritten on the next\n",
    "    iteration. To jump, use `while` with your own index.\n",
    "  - `enumerate(s[i:])` numbers the slice from 0, not from `i`, so the indexes were off by `i`.\n",
    "    `s.find(\"#\", i)` searches from `i` and returns an index in `s`.\n",
    "  - Added `if len(s) == 1` to patch a symptom: no encoded string has length 1. Fix the cause\n",
    "    rather than special-casing one input.\n",
    "- **Related problems:** Serialize and Deserialize Binary Tree (#297, same encode/decode design\n",
    "  for a tree), String Compression (#443, writing counts into a string), Decode String (#394,\n",
    "  parsing a number followed by content), Count and Say (#38, reading runs of digits)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}