code/680. Valid Palindrome II.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem\n",
    "\n",
    "Given a string `s`, return `true` *if the* `s` *can be palindrome after deleting **at most one** character from it*.\n",
    "\n",
    " \n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "```\n",
    "Input: s = \"aba\"\n",
    "Output: true\n",
    "```\n",
    "\n",
    "**Example 2:**\n",
    "\n",
    "```\n",
    "Input: s = \"abca\"\n",
    "Output: true\n",
    "Explanation: You could delete the character 'c'.\n",
    "```\n",
    "\n",
    "**Example 3:**\n",
    "\n",
    "```\n",
    "Input: s = \"abc\"\n",
    "Output: false\n",
    "```\n",
    "\n",
    " \n",
    "\n",
    "**Constraints:**\n",
    "\n",
    "- `1 <= s.length <= 10^5`\n",
    "- `s` consists of lowercase English letters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary\n",
    "\n",
    "The problem can de divided into two parts:\n",
    "\n",
    "+ search the outlier character;\n",
    "+ check palindrome.\n",
    "\n",
    "Thus, we can utilize different methods to search, like binary search, linear search, recursive search.\n",
    "\n",
    "`>>` can be used to implement binary search\n",
    "\n",
    "Another important point in this problem is the memory cost. With the fancy search methods, we can compare the shallow copy string at least times, which reduces the memory cost."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Methods\n",
    "\n",
    "Two methods:\n",
    "\n",
    "+ Brute force deletes the character and check palindrome after the deletion.\n",
    "+ Two pointer moves from the beginning of the string and from the last character of the string simultaneously, if they find a different character pair, then check the palindromic of the left side and right side string.\n",
    "\n",
    "However, we can implement the two pointer in different ways, and which results in different time complexity and space complexity:\n",
    "\n",
    "+ Naive two pointer: move one by one;\n",
    "+ Binary two pointer (state-of-art): reduce the movement in log;\n",
    "+ Recursive two pointer: move one by one."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Method 1 [DEPRECATED] Brute Force\n",
    "\n",
    "+ **Time Complexity**: $O(n)$\n",
    "+ **Space Complexity**: $O(n)$\n",
    "+ $n$ is the string length.\n",
    "\n",
    "OUT OF TIME."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            for i in range(1, len(s) + 1):\n",
    "                new_s = ''.join([s[:i-1], s[i:]])\n",
    "                if new_s == new_s[::-1]:\n",
    "                    return True\n",
    "\n",
    "            return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Method 2 Two Pointer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Version 1 [DEPRECATED] Naive Two Pointer\n",
    "\n",
    "The idea is the compare the two character at the same position, if the two character are different, then move to the next character and compare but don't accept difference for the following comparisons.\n",
    "\n",
    "One important issue is I don't know how to determine which side is to be needed to move, if two side are available. For example, 'ab...ab'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        pointer = 0\n",
    "        anchor = len(s) - 1\n",
    "        cnt = 0\n",
    "\n",
    "        while cnt <= 1 and pointer <= anchor:\n",
    "            if s[pointer] == s[anchor]:\n",
    "                pointer += 1\n",
    "                anchor -= 1\n",
    "            else:\n",
    "                if s[pointer + 1] == s[anchor]:\n",
    "                    pointer += 2\n",
    "                    anchor -= 1\n",
    "                    cnt += 1\n",
    "                elif s[pointer] == s[anchor - 1]:\n",
    "                    pointer += 1\n",
    "                    anchor -= 2\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        return cnt <= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Version 2 Two Pointer & Holistic Comparison\n",
    "\n",
    "+ **Time Complexity**: $O(n/2)$\n",
    "+ **Space Complexity**: $O(2n)$\n",
    "\n",
    "This method creates two shallow copy of the string, thus it yields a lot of memory cost."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        pointer = 0\n",
    "        anchor = len(s) - 1\n",
    "\n",
    "        while pointer <= anchor:\n",
    "            if s[pointer] == s[anchor]:\n",
    "                pointer += 1\n",
    "                anchor -= 1\n",
    "            else:\n",
    "                if s[pointer + 1] == s[anchor] and s[pointer] != s[anchor - 1]:\n",
    "                    return s[pointer + 1:anchor + 1] == s[pointer + 1:anchor + 1][::-1]\n",
    "                elif s[pointer] == s[anchor - 1] and s[pointer + 1] != s[anchor]:\n",
    "                    return s[pointer:anchor] == s[pointer:anchor][::-1]\n",
    "                elif s[pointer] == s[anchor - 1] and s[pointer + 1] == s[anchor]:\n",
    "                    return s[pointer + 1:anchor + 1] == s[pointer + 1:anchor + 1][::-1] or s[pointer:anchor] == s[pointer:anchor][::-1]\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        pointer = 0\n",
    "        anchor = len(s) - 1\n",
    "\n",
    "        while pointer <= anchor:\n",
    "            if s[pointer] == s[anchor]:\n",
    "                pointer += 1\n",
    "                anchor -= 1\n",
    "            else:\n",
    "                return s[pointer + 1:anchor + 1] == s[pointer + 1:anchor + 1][::-1] or s[pointer:anchor] == s[pointer:anchor][::-1]\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Version 3 [State-of-Art] `>>` \n",
    "\n",
    "+ **Time Complexity**: $O(\\log{n})$\n",
    "+ **Space Complexity**: $O(n)$\n",
    "\n",
    "~~The logic is the same as the version 2, but rather using a binary pruning method to decide the length of the shallow copy.~~\n",
    "\n",
    "`x >> y`: Returns x with the bits shifted to the right by y places. This is the same as //'ing x by 2**y.<sup>[1](#ft1)</sup>\n",
    "\n",
    "The logic over here seems tricky. \n",
    "\n",
    "By following the steps, I may can tackle the logic:\n",
    "\n",
    "+ The first iteration, `i, j, x = 0, len(s) - 1, lens(s) >>1`,  \n",
    "\n",
    "    + if the first half string is the same as the second half string, `i += x, j -= x` => `i = len(s) >> 1, j = len(s) - len(s) >>1` => \n",
    "        + if `len(s)` is even, `return True`;\n",
    "        + else continue the `while` statement.\n",
    "    + else, stay in `i` and `j`, and compare the first quarter string and the last quarter string if and only if `x > 1`.\n",
    "        + if `x == 1`, move to compare the right side of `i` or the left side of `j`.\n",
    "\n",
    "Yes, the logic is the same as the version 2, but not like the version 2 moves one step by step, version 3 moves in a binary degree. Once it find one character is different from another, then it starts to compare the two-side string.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        helper = lambda s: s == s[::-1]\n",
    "        \n",
    "        i, j, x = 0, len(s) - 1, len(s) >> 1\n",
    "        \n",
    "        while i < j:\n",
    "            if s[i: i + x] == s[j: j - x: -1]:\n",
    "                i += x\n",
    "                j -= x\n",
    "            elif x > 1:\n",
    "                x >>= 1\n",
    "            else:\n",
    "                return helper(s[i: j]) or helper(s[i + 1: j + 1])\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Version 4 Recursive <sup>[2](#ft2)</sup>\n",
    "\n",
    "+ **Time Complexity**: $O(n)$\n",
    "+ **Space Complexity**: $O(n)$\n",
    "\n",
    "This method shares the same idea with the previous, but adding a `count` parameter into the recursive function to count the different character pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        l, r = 0, len(s)-1\n",
    "        count = 0\n",
    "                    \n",
    "        def isPalindrome(l, r, count):\n",
    "            if count > 1:\n",
    "                return False\n",
    "            while l < r:\n",
    "                if s[l] == s[r]:\n",
    "                    l+=1\n",
    "                    r-=1\n",
    "                if s[l] != s[r]:\n",
    "                    if s[l+1] != s[r] and s[l] != s[r-1]:\n",
    "                        return False\n",
    "                    return isPalindrome(l+1, r, count+1) or isPalindrome(l, r-1, count+1)\n",
    "\t\t\t\t\t\n",
    "            return True\n",
    "        \n",
    "        return isPalindrome(l, r, count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Footnotes\n",
    "\n",
    "<a name=\"ft1\">[1]</a>: https://wiki.python.org/moin/BitwiseOperators\n",
    "\n",
    "<a name=\"ft2\">[2]</a>: https://leetcode.com/problems/valid-palindrome-ii/discuss/723091/Python%3A-Short-and-easy-to-understand-recursive-solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add the doc information to README\n",
    "from tools.setup import generate_row as g\n",
    "\n",
    "g()"
   ]
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.11"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}