题目描述
思路解析
一句话答案：LeetCode 1898 可移除字符的最大数目：p 本是 s 的子序列，按 removable 抹得越多越易断，求还能保住 p 的最大 k。抹越多越难保住这条单调让 k 可二分，两指针验子序列。时间 O(n·log m)、空间 O(n)。
抹掉一批下标还想保住 p，这题在求哪个 k
给字符串 s 和 p，p 本来就是 s 的子序列——从 s 里按原顺序挑若干字符拼成 p，可跳过但不能打乱次序。再给下标数组 removable，你按它的顺序取前 k 个，把这些位置的字符从 s 抹掉（按下标抹）。抹得越多 p 越可能断，求最大的 k 让抹完后 p 还是子序列。题面 s=abcacb、p=ab、removable=[3,1,0] 时答案 2。
从抹满往下一个个退着试 k，慢在哪
从最多的 m 个往下试是能做的（m 是 removable 长度）：抹满 m 个不行就退一个再问，直到碰上能保住 p 的 k。可每个 k 都要两指针扫一遍 s 判子序列，一趟 O(n)（n 是 s 长度）；最坏从 m 退到答案，合起来 O(n·m)，规模一大就压不动。
移除得越多越难保住 p，可行的 k 就到某一点为止
抹的下标越多 s 剩的字符越少、配出 p 更难，抹得越少越容易。可行性沿这一个方向铺开、到某点翻面一次就不再翻回来，这就是单调：可行的 k 连成前一段、不可行的连成后一段。有了它就能像有序序列里找边界那样，猜一个 k、验它可不可行，再决定往大往小收——这正是二分答案的路子。二分的是能删几个、不是 s 的下标。
判定函数怎么写，可行和不可行各往哪半收
判定函数 check(k)：用布尔数组 rem 把 removable 前 k 个下标标成已移除；再两指针 i 扫 s、j 指 p 当前要配的字符，遇到没移除且等于 p[j] 的位置就配上、j 推一格，扫完看 j 到没到 p 末尾。二分取闭区间 [l,r]、l=0、r=m，每轮 mid=(l+r+1)//2，加 1 让中点偏右取整：check(mid) 为真还能抹更多、l 收到 mid，为假就 r 退到 mid-1。缩到 l 和 r 撞上就是答案。
拿题面 abcacb、[3,1,0] 逐轮列 l、r、mid
拿 s=abcacb（下标 0-5 依次 a、b、c、a、c、b）、p=ab、removable=[3,1,0] 走。l=0、r=3。第一轮 mid=(0+3+1)//2=2，check(2) 抹下标 3、1：下标 0 配上 a，1 和 3 跳过，2、4 的 c 配不上 b，下标 5 配上 b、j 到 2 配齐，可行，l 收到 2。第二轮 mid=3，check(3) 再抹下标 0：只剩 c、c、b，p 的 a 没处配，不可行，r 退到 2。此时 l=r=2，返回 2。
二分的是移除个数，别架到 s 的下标上去
复杂度：二分约 log m 轮、每轮扫一遍 s，时间 O(n·log m)；每次 check 开一个和 s 等长的 rem 数组，空间峰值 O(n)。三处最坑。一是以为在 s 里找位置、把二分架到 s 下标上，其实 s 不用有序，二分的是移除个数、范围 0 到 m。二是方向收反：check(k) 为真还能抹更多、该 l=mid，收反了会得偏小的错答案。三是 mid 用 (l+r)//2 向下取整又配 l=mid，只剩两数时 l 不动就卡死，得写 (l+r+1)//2 偏右取整。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢:抹得越少越容易保住 p,可行性单调,于是在 0 到 removable.length 上二分移除个数 k。检查一个 k:标红前 k 个下标,两指针从左到右贪心配 p,j 配齐 p 则可行、收左界,否则收右界。二分的是移除个数,不是下标。
总览 · 想尽量多抹几个还保住 p：先看清画面。上面这排格子是 s 等于 abcabc,下面数字是它们的下标 0 到 5。removable 等于 5,3,4,1,0,2,意思是要抹字符时,先抹下标 5、再下标 3、再下标 4,依此类推。p 等于 abc,现在它是 s 的子序列,拿开头的 a、b、c 就能配出来。我们要在保住 p 的前提下,尽量多抹几个下标。右边面板记着 p、下标行、移除个数的范围、当前检验的 k、以及配 p 的进度。
定范围 · 在 0 到 6 上二分移除个数：先框定答案范围。最少可以一个都不抹,那 k 等于 0;最多把 removable 里全部 6 个下标都抹掉,那 k 等于 6。所以答案一定落在 0 到 6 这个闭区间里。接下来不逐个试,而是二分:取中点当候选 k,标红前 k 个下标,再用两指针验证 p 还配不配得出来。请记住,右边面板里动的是移除个数 k 的范围,不是 s 的下标,s 这排字符始终不动。
第一轮 · 取中点 k = 3：开始第一轮二分。当前范围 0 到 6,取中点,k 等于 0 加 6 加 1 再整除 2 得 3。这里加 1 是让中点偏右取整,配合后面收界的写法,防止二分死循环。也就是先问:抹掉 removable 前 3 个下标,p 还是 s 的子序列吗?
第一轮 · 抹掉下标 5, 3, 4：取 removable 的前 3 个下标 5, 3, 4,把 s 里这几个位置标红,当作已经抹掉。剩下没标红的字符,按原来的顺序还留在 s 里。接着让指针 i 从左往右扫 s,指针 j 指向 p 当前要配的字符,先要配的是 a。只有没被抹掉、又正好等于 p 当前字符的位置,才能把 j 往前推。
第一轮 · 扫下标 0 配上 a：开始扫 s。下标 0 是 a,正好等于 p 当前要配的 a,配上了,标绿,j 往前推一格,接下来等 b。
第一轮 · 扫下标 1 配上 b：下标 1 是 b,正好等于 p 当前要配的 b,配上了,标绿,j 往前推一格,接下来等 c。
第一轮 · 扫下标 2 配上 c：下标 2 是 c,正好等于 p 当前要配的 c,配上了,标绿,j 往前推一格,p 已经配齐。
第一轮 · k = 3 可行：扫完了,j 走到了 3,p 的三个字符全配上,说明抹掉前 3 个下标以后 p 还是子序列,这个 k 可行。既然能抹 3 个,那就想能不能抹更多,把左界收到 3,范围变成 3 到 6。注意左界取 3 而不是 3 加 1,因为 3 本身也可能就是最终答案,要留着。
第二轮 · 取中点 k = 5：第二轮二分。上一轮把范围收到了 [3, 6],取中点得到候选 k 等于 5。同样地问一句:抹掉 removable 前 5 个下标,p 还配得出来吗?
第二轮 · 抹掉下标 5, 3, 4, 1, 0：取 removable 的前 5 个下标 5, 3, 4, 1, 0,把 s 里这几个位置标红,当作已经抹掉。剩下没标红的字符,按原来的顺序还留在 s 里。接着让指针 i 从左往右扫 s,指针 j 指向 p 当前要配的字符,先要配的是 a。只有没被抹掉、又正好等于 p 当前字符的位置,才能把 j 往前推。
第二轮 · 扫下标 0 已移除：开始扫 s。指针 i 走到下标 0,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
第二轮 · 扫下标 1 已移除：指针 i 走到下标 1,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
第二轮 · 扫下标 2 配不上：下标 2 是 c,和 p 当前要配的 a 不一样,配不上,i 右移接着看,j 不动。
第二轮 · 扫下标 3 已移除：指针 i 走到下标 3,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
第二轮 · 扫下标 4 已移除：指针 i 走到下标 4,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
第二轮 · 扫下标 5 已移除：指针 i 走到下标 5,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
第二轮 · k = 5 不可行：扫完了,j 只走到 0,还差 a 没配上,p 被抹断了,说明抹 5 个太狠。那 5 以及更多都不行,把右界收到 4,范围变成 3 到 4。继续在更小的个数里试。
第三轮 · 取中点 k = 4：第三轮二分。上一轮把范围收到了 [3, 4],取中点得到候选 k 等于 4。同样地问一句:抹掉 removable 前 4 个下标,p 还配得出来吗?
第三轮 · 抹掉下标 5, 3, 4, 1：取 removable 的前 4 个下标 5, 3, 4, 1,把 s 里这几个位置标红,当作已经抹掉。剩下没标红的字符,按原来的顺序还留在 s 里。接着让指针 i 从左往右扫 s,指针 j 指向 p 当前要配的字符,先要配的是 a。只有没被抹掉、又正好等于 p 当前字符的位置,才能把 j 往前推。
第三轮 · 扫下标 0 配上 a：开始扫 s。下标 0 是 a,正好等于 p 当前要配的 a,配上了,标绿,j 往前推一格,接下来等 b。
第三轮 · 扫下标 1 已移除：指针 i 走到下标 1,这个位置已经被抹掉了,直接跳过,j 不动,还在等 b。
第三轮 · 扫下标 2 配不上：下标 2 是 c,和 p 当前要配的 b 不一样,配不上,i 右移接着看,j 不动。
第三轮 · 扫下标 3 已移除：指针 i 走到下标 3,这个位置已经被抹掉了,直接跳过,j 不动,还在等 b。
第三轮 · 扫下标 4 已移除：指针 i 走到下标 4,这个位置已经被抹掉了,直接跳过,j 不动,还在等 b。
第三轮 · 扫下标 5 已移除：指针 i 走到下标 5,这个位置已经被抹掉了,直接跳过,j 不动,还在等 b。
第三轮 · k = 4 不可行：扫完了,j 只走到 1,还差 b 没配上,p 被抹断了,说明抹 4 个太狠。那 4 以及更多都不行,把右界收到 3,范围变成 3 到 3。左右界撞到一起,二分到此收束。
收束 · 左右界重合于 3：二分收束了。左界和右界都停在 3,说明 3 是能保住 p 的最多移除个数:抹 3 个时 p 还在,而抹到 4 个就被抹断了。抹掉前 3 个下标 5, 3, 4 后,s 剩下 abc,p 正好配得上。
完成 · 最大移除个数 = 3：收个尾。这道题的巧劲在于把「最多能抹几个」这个不好直接求的问题,翻译成「抹 k 个还保不保得住 p」这个好判断的问题,再靠可行性单调二分 k。s 等于 abcabc、p 等于 abc、removable 等于 5,3,4,1,0,2,我们只检验了 3 个候选 k,就锁定最大移除个数是 3。二分把候选个数从线性压成对数级,每次可行性检查线性扫一遍 s,又快又稳。
边界:removable 第一个就抹掉 p 唯一配头则答案 0;若全抹完 p 还在则答案就是 removable.length;p 只有一个字符时,抹到把它最后一个来源也抹掉的前一步为止。都能用可行性检查逐个验证。
面试重点:抹得越少越容易保住 p,可行性单调所以能二分 k;可行性用贪心两指针判子序列,选最靠左能配的位置最优;朴素 O(n log m) 已够,进一步优化可预处理但先写对标准解。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int: def check(k: int) -> bool: rem = [False] * len(s) for i in removable[:k]: rem[i] = True i = j = 0 while i < len(s) and j < len(p): if not rem[i] and p[j] == s[i]: j += 1 i += 1 return j == len(p) l, r = 0, len(removable) while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return l复杂度
- 时间：O(n log m)，n 是 s 的长度,m 是 removable 的长度。二分在 0 到 m 上进行,最多 log m 轮;每一轮做一次可行性检查,要新开并标记 rem 数组、再两指针扫一遍 s,都是 O(n)。两者相乘就是 O(n log m)。演示里 n 等于 6、m 等于 6,只检验了 3 个候选 k 就收敛
- 空间：O(n)，按峰值算。每次可行性检查都新开一个和 s 等长的布尔数组 rem 来标记哪些下标被移除,它的大小是 n,这是额外空间的峰值。除此之外只有 lo、hi、mid、i、j 几个标量。所以额外空间是 O(n),不是常数
易错点
面试追问把动画讲成自己的话
追问为什么移除个数 k 可以拿来二分?单调性体现在哪?
追问可行性检查里为什么用贪心两指针判子序列就对?
追问每次检查都重新扫一遍 s,有没有办法更快?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
考试的最大困扰度
LeetCode 2024 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题