二分查找_1898.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [1898. 可移除字符的最大数目](https://leetcode.cn/problems/maximum-number-of-removable-characters)\n",
    "\n",
    "[English Version](/solution/1800-1899/1898.Maximum%20Number%20of%20Removable%20Characters/README_EN.md)\n",
    "\n",
    "## 题目描述\n",
    "\n",
    "<!-- 这里写题目描述 -->\n",
    "\n",
    "<p>给你两个字符串 <code>s</code> 和 <code>p</code> ，其中 <code>p</code> 是 <code>s</code> 的一个 <strong>子序列</strong> 。同时，给你一个元素 <strong>互不相同</strong> 且下标 <strong>从 0 开始</strong> 计数的整数数组 <code>removable</code> ，该数组是 <code>s</code> 中下标的一个子集（<code>s</code> 的下标也 <strong>从 0 开始</strong> 计数）。</p>\n",
    "\n",
    "<p>请你找出一个整数 <code>k</code>（<code>0 <= k <= removable.length</code>），选出 <code>removable</code> 中的 <strong>前</strong> <code>k</code> 个下标，然后从 <code>s</code> 中移除这些下标对应的 <code>k</code> 个字符。整数 <code>k</code> 需满足：在执行完上述步骤后， <code>p</code> 仍然是 <code>s</code> 的一个 <strong>子序列</strong> 。更正式的解释是，对于每个 <code>0 <= i < k</code> ，先标记出位于 <code>s[removable[i]]</code> 的字符，接着移除所有标记过的字符，然后检查 <code>p</code> 是否仍然是 <code>s</code> 的一个子序列。</p>\n",
    "\n",
    "<p>返回你可以找出的 <strong>最大</strong><em> </em><code>k</code><em> </em>，满足在移除字符后<em> </em><code>p</code><em> </em>仍然是 <code>s</code> 的一个子序列。</p>\n",
    "\n",
    "<p>字符串的一个 <strong>子序列</strong> 是一个由原字符串生成的新字符串，生成过程中可能会移除原字符串中的一些字符（也可能不移除）但不改变剩余字符之间的相对顺序。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcacb\", p = \"ab\", removable = [3,1,0]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>在移除下标 3 和 1 对应的字符后，\"a<strong>b</strong>c<strong>a</strong>cb\" 变成 \"accb\" 。\n",
    "\"ab\" 是 \"<strong>a</strong>cc<strong>b</strong>\" 的一个子序列。\n",
    "如果移除下标 3、1 和 0 对应的字符后，\"<strong>ab</strong>c<strong>a</strong>cb\" 变成 \"ccb\" ，那么 \"ab\" 就不再是 s 的一个子序列。\n",
    "因此，最大的 k 是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcbddddd\", p = \"abcd\", removable = [3,2,1,4,5,6]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>在移除下标 3 对应的字符后，\"abc<strong>b</strong>ddddd\" 变成 \"abcddddd\" 。\n",
    "\"abcd\" 是 \"<strong>abcd</strong>dddd\" 的一个子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcab\", p = \"abc\", removable = [0,1,2,3,4]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>如果移除数组 removable 的第一个下标，\"abc\" 就不再是 s 的一个子序列。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= p.length <= s.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= removable.length < s.length</code></li>\n",
    "\t<li><code>0 <= removable[i] < s.length</code></li>\n",
    "\t<li><code>p</code> 是 <code>s</code> 的一个 <strong>子字符串</strong></li>\n",
    "\t<li><code>s</code> 和 <code>p</code> 都由小写英文字母组成</li>\n",
    "\t<li><code>removable</code> 中的元素 <strong>互不相同</strong></li>\n",
    "</ul>\n",
    "\n",
    "## 解法\n",
    "\n",
    "<!-- 这里可写通用的实现逻辑 -->\n",
    "\n",
    "**方法一：二分查找 + 判断子序列**\n",
    "\n",
    "二分枚举整数 k，找到满足要求的最大 k 即可。\n",
    "\n",
    "以下是二分查找的两个通用模板：\n",
    "\n",
    "模板 1：\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 子字符串的匹配最快是KMP，子序列最快则是双指针\n",
    "子序列的匹配只需要顺序相同即可\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 本题目有两个坑点：\n",
    "#### 其一是做母串和子串比对时，请先比对短的那个的长度，再比对长的那个的长度\n",
    "#### 其二是这道题k的范围为[0,len()],而k所在的值又是不满足条件的，所以返回的是right\n",
    "left=1，right=len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "#搜索子序列的函数\n",
    "def search_subsequence(target:str,sub_string:str)->bool:\n",
    "    i,j=0,0\n",
    "    while i!=len(target) and j!=len(sub_string):\n",
    "        if target[i]==sub_string[j]:\n",
    "            j+=1\n",
    "        else:\n",
    "            pass\n",
    "        i+=1\n",
    "    if j==len(sub_string):\n",
    "        return  True\n",
    "    if i==len(target):#最长的\n",
    "        return False\n",
    "if  __name__==\"__main__\":\n",
    "    print(search_subsequence(\"acb\",\"ab\"))\n",
    "    print(search_subsequence(\"acb\",\"ac\"))\n",
    "    print(search_subsequence(\"acb\",\"ad\"))\n",
    "    print(search_subsequence(\"acb\",\"ba\"))\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[0,1,2,3]\n",
    "3(right)\n",
    "[1,2,3]\n",
    "(right=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:\n",
    "        def search_subsequence(removable_set:set)->bool:\n",
    "            i,j=0,0\n",
    "            # print(\"set\",removable_set)\n",
    "            while i!=len(s) and j!=len(p):\n",
    "                if i in removable_set:\n",
    "                    i+=1\n",
    "                    continue\n",
    "                if s[i]==p[j]:\n",
    "                    j+=1\n",
    "                else:\n",
    "                    pass\n",
    "                i+=1\n",
    "            # print(i,j,len(p))\n",
    "            if j==len(p):##先匹配目标串\n",
    "                return True\n",
    "            if i==len(s):\n",
    "                return False\n",
    "            \n",
    "        left,right=0,len(removable)\n",
    "        while left<=right:\n",
    "            mid=left+((right-left)>>1)\n",
    "            removable_set=set(removable[:mid])#mid是最大不包含的\n",
    "            # print(left,right,mid)\n",
    "            if search_subsequence(removable_set=removable_set):#是子序列\n",
    "                left=mid+1\n",
    "                # print(\"true\")\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return right\n",
    "        \n",
    "if  __name__==\"__main__\":\n",
    "    solution=Solution()\n",
    "    # 2 1 0\n",
    "    print(solution.maximumRemovals(\"abcacb\",\"ab\",[3,1,0]))\n",
    "    #\"abcbddddd\", p = \"abcd\", removable = [3,2,1,4,5,6]\n",
    "    print(solution.maximumRemovals(\"abcbddddd\",\"abcd\",[3,2,1,4,5,6]))\n",
    "    #s = \"abcab\", p = \"abc\", removable = [0,1,2,3,4]\n",
    "    print(solution.maximumRemovals(\"abcab\",\"abc\",[0,1,2,3,4]))   \n",
    "    \n",
    "    "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.12 ('base')",
   "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.9.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "7b93ae2ddedcfb4b7ddebf80c8c7984044339b2e43f10e14b9461f3e640893f2"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}