可移除字符的最大数目

记牢:抹得越少越容易保住 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) 已够,进一步优化可预处理但先写对标准解。