{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "62ceed570a34",
   "metadata": {},
   "source": [
    "# Valid Palindrome\n",
    "\n",
    "| Field      | Value                                   |\n",
    "|------------|-----------------------------------------|\n",
    "| Source     | [link](https://leetcode.com/problems/valid-palindrome/)  |\n",
    "| Difficulty | Easy                    |\n",
    "| Topics     | `two pointers`, `string`                     |\n",
    "| Date       | 2026-10-14                              |\n",
    "| Status     | Solved                                  |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2427e19c74fd",
   "metadata": {},
   "source": [
    "## 1. Problem\n",
    "\n",
    "> Given a string `s`, return `true` if it is a palindrome, otherwise return `false`.\n",
    "> A palindrome is a string that reads the same forward and backward. It is also\n",
    "> case-insensitive and ignores all non-alphanumeric characters.\n",
    "> (Alphanumeric characters are letters `A-Z`, `a-z` and digits `0-9`.)\n",
    "\n",
    "**Example 1**\n",
    "```\n",
    "Input:  s = \"Was it a car or a cat I saw?\"\n",
    "Output: true\n",
    "```\n",
    "After keeping only alphanumerics and lowercasing: `\"wasitacaroracatisaw\"`, a palindrome.\n",
    "\n",
    "**Example 2**\n",
    "```\n",
    "Input:  s = \"tab a cat\"\n",
    "Output: false\n",
    "```\n",
    "`\"tabacat\"` is not a palindrome.\n",
    "\n",
    "**Constraints**\n",
    "- `1 <= len(s) <= 1000`\n",
    "- `s` is made up of only printable ASCII characters."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7e325500ec8",
   "metadata": {},
   "source": [
    "## 2. Thinking\n",
    "\n",
    "- **Brute force idea:** build a cleaned copy (alphanumerics only, lowercased), reverse it and\n",
    "  compare → $O(n)$ time, but $O(n)$ extra space for the copy and its reverse.\n",
    "- **Key insight:** a palindrome means `s[i]` matches `s[n-1-i]`. So compare from **both ends\n",
    "  inward with two pointers**, skipping characters that don't count. No copy needed → $O(1)$ space.\n",
    "- **Edge cases to remember:** a string with no alphanumerics at all (`\"?!\"`, `\" \"`) is a\n",
    "  palindrome (the empty string); mixed case (`\"Aa\"`); digits count (`\"0P\"` is **not** a palindrome);\n",
    "  the skip loops must also check `left < right` so they can't run off the end."
   ]
  },
  {
   "cell_type": "code",
   "id": "ce38f316df69",
   "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": "64c76e7e91b3",
   "metadata": {},
   "source": [
    "## 3. Solution\n",
    "\n",
    "### Approach A — my solution (two pointers, skip non-alphanumerics) ✅ best practice\n",
    "**Complexity:** Time $O(n)$ · Space $O(1)$\n",
    "\n",
    "Already optimal: each pointer only moves inward, so every character is visited at most once,\n",
    "and nothing is copied. The inner `while` loops guard with `left < right`, so a string full of\n",
    "punctuation can't push the pointers out of bounds."
   ]
  },
  {
   "cell_type": "code",
   "id": "b0955c53dbb6",
   "metadata": {},
   "source": [
    "def is_palindrome(s: str) -> bool:\n",
    "    left = 0\n",
    "    right = len(s) - 1\n",
    "\n",
    "    while left < right:\n",
    "        while left < right and not s[left].isalnum():\n",
    "            left += 1\n",
    "        while left < right and not s[right].isalnum():\n",
    "            right -= 1\n",
    "        if s[left].lower() != s[right].lower():\n",
    "            return False\n",
    "        left += 1\n",
    "        right -= 1\n",
    "    return True"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "b948cf72a950",
   "metadata": {},
   "source": [
    "### Approach B — clean, then compare with the reverse (Pythonic)\n",
    "**Complexity:** Time $O(n)$ · Space $O(n)$ (the cleaned string and its reversed copy)\n",
    "\n",
    "The brute force from the hints. Shortest to write, and fast in practice because the\n",
    "work happens in C, but it uses extra memory, which is what the follow-up asks you to avoid."
   ]
  },
  {
   "cell_type": "code",
   "id": "fb13f69bc9d1",
   "metadata": {},
   "source": [
    "def is_palindrome_reverse(s: str) -> bool:\n",
    "    cleaned = \"\".join(c.lower() for c in s if c.isalnum())\n",
    "    return cleaned == cleaned[::-1]"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "09215d098398",
   "metadata": {},
   "source": [
    "## 4. Tests\n",
    "\n",
    "Both implementations run against the same cases."
   ]
  },
  {
   "cell_type": "code",
   "id": "4bbc1acb043b",
   "metadata": {},
   "source": [
    "%%ipytest -q\n",
    "\n",
    "CASES = [\n",
    "    (\"Was it a car or a cat I saw?\", True),\n",
    "    (\"tab a cat\", False),\n",
    "    (\"A man, a plan, a canal: Panama\", True),\n",
    "    (\"race a car\", False),\n",
    "    (\" \", True),                 # no alphanumerics -> empty string -> palindrome\n",
    "    (\"?!.,\", True),              # only punctuation\n",
    "    (\"a\", True),                 # single character\n",
    "    (\"Aa\", True),                # case-insensitive\n",
    "    (\"0P\", False),               # digits count; '0' != 'p'\n",
    "    (\"ab\", False),               # two different letters\n",
    "    (\".a.\", True),               # non-alphanumerics on both ends\n",
    "    (\"a.b,.a\", True),            # skips in the middle\n",
    "    (\"12321\", True),             # digits only\n",
    "    (\"ab\" * 500, False),         # max length, not a palindrome\n",
    "    (\"a\" * 999 + \"!\", True),     # max length, skip at the end\n",
    "]\n",
    "\n",
    "@pytest.mark.parametrize(\"fn\", [is_palindrome, is_palindrome_reverse])\n",
    "@pytest.mark.parametrize(\"s, expected\", CASES)\n",
    "def test_is_palindrome(fn, s, expected):\n",
    "    assert fn(s) == expected"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "8d7d7e88b873",
   "metadata": {},
   "source": [
    "## 5. Scratch / Experiments\n",
    "\n",
    "Worst case: a real palindrome (so neither approach can exit early) at the maximum length of 1000\n",
    "characters, with punctuation and mixed case so the skipping and lowercasing do work.\n",
    "\n",
    "Approach B is usually faster in wall-clock time despite the extra memory: its loop is a\n",
    "generator feeding `str.join`, and `[::-1]` and `==` run in C, while Approach A's pointer loop\n",
    "runs line by line in Python. Same $O(n)$ time; A wins on space, which is the point of the\n",
    "question."
   ]
  },
  {
   "cell_type": "code",
   "id": "077420e7d5f6",
   "metadata": {},
   "source": [
    "import random, string\n",
    "\n",
    "half = \"\".join(random.choices(string.ascii_letters + string.digits + \" ,.!?\", k=500))\n",
    "s = half + half[::-1].swapcase()  # mirror with flipped case: still a palindrome\n",
    "assert is_palindrome(s) and is_palindrome_reverse(s)\n",
    "%timeit is_palindrome(s)\n",
    "%timeit is_palindrome_reverse(s)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "b6578dfe8411",
   "metadata": {},
   "source": [
    "## 6. Takeaways\n",
    "\n",
    "- **Pattern:** \"compare the start with the end\" (palindromes, reversing in place, pair sums on a\n",
    "  sorted array) → **two pointers moving inward**, $O(1)$ space. When some elements must be\n",
    "  ignored, skip them with inner `while` loops that **also check `left < right`**.\n",
    "- **Mistakes I made:** none in the algorithm, it's the optimal solution. Things to keep doing:\n",
    "  the bounds guard in the skip loops, and comparing `.lower()` on both sides instead of building\n",
    "  a lowercase copy. (Note: `str.isalnum()` also accepts Unicode letters/digits like `'é'` or `'²'`;\n",
    "  fine here since the input is ASCII.)\n",
    "- **Related problems:** Valid Palindrome II (#680, same two pointers, allow one deletion),\n",
    "  Two Sum II (#167, two pointers on a sorted array), Reverse String (#344, swap from both ends),\n",
    "  Longest Palindromic Substring (#5, expand from the center instead of shrinking from the ends),\n",
    "  Palindrome Linked List (#234, no random access, so reverse the second half)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}