可移除字符的最大数目 图解题解
这道题到底在问什么
- 输入
- s=abcacb, p=ab, removable=[3,1,0]
- 输出
- 2
- 输入
- s=abcbddddd, p=abcd, removable=[3,2,1,4,5,6]
- 输出
- 1
- 输入
- s=abcab, p=abc, removable=[0,1,2,3,4]
- 输出
- 0
最优解：一步一步想明白
- 3记牢:抹得越少越容易保住 p,可行性单调,于是在 0 到 removable.length 上二分移除个数 k。检查一个 k:标红前 k 个下标,两指针从左到右贪心配 p,j 配齐 p 则可行、收左界,否则收右界。二分的是移除个数,不是下标。
- 4先看清画面。上面这排格子是 s 等于 abcabc,下面数字是它们的下标 0 到 5。removable 等于 5,3,4,1,0,2,意思是要抹字符时,先抹下标 5、再下标 3、再下标 4,依此类推。p 等于 abc,现在它是 s 的子序列,拿开头的 a、b、c 就能配出来。我们要在保住 p 的前提下,尽量多抹几个下标。右边面板记着 p、下标行、移除个数的范围、当前检验的 k、以及配 p 的进度。
- 5先框定答案范围。最少可以一个都不抹,那 k 等于 0;最多把 removable 里全部 6 个下标都抹掉,那 k 等于 6。所以答案一定落在 0 到 6 这个闭区间里。接下来不逐个试,而是二分:取中点当候选 k,标红前 k 个下标,再用两指针验证 p 还配不配得出来。请记住,右边面板里动的是移除个数 k 的范围,不是 s 的下标,s 这排字符始终不动。
- 6开始第一轮二分。当前范围 0 到 6,取中点,k 等于 0 加 6 加 1 再整除 2 得 3。这里加 1 是让中点偏右取整,配合后面收界的写法,防止二分死循环。也就是先问:抹掉 removable 前 3 个下标,p 还是 s 的子序列吗?
- 7取 removable 的前 3 个下标 5, 3, 4,把 s 里这几个位置标红,当作已经抹掉。剩下没标红的字符,按原来的顺序还留在 s 里。接着让指针 i 从左往右扫 s,指针 j 指向 p 当前要配的字符,先要配的是 a。只有没被抹掉、又正好等于 p 当前字符的位置,才能把 j 往前推。
- 8开始扫 s。下标 0 是 a,正好等于 p 当前要配的 a,配上了,标绿,j 往前推一格,接下来等 b。
- 9下标 1 是 b,正好等于 p 当前要配的 b,配上了,标绿,j 往前推一格,接下来等 c。
- 10下标 2 是 c,正好等于 p 当前要配的 c,配上了,标绿,j 往前推一格,p 已经配齐。
- 11扫完了,j 走到了 3,p 的三个字符全配上,说明抹掉前 3 个下标以后 p 还是子序列,这个 k 可行。既然能抹 3 个,那就想能不能抹更多,把左界收到 3,范围变成 3 到 6。注意左界取 3 而不是 3 加 1,因为 3 本身也可能就是最终答案,要留着。
- 12第二轮二分。上一轮把范围收到了 [3, 6],取中点得到候选 k 等于 5。同样地问一句:抹掉 removable 前 5 个下标,p 还配得出来吗?
- 13取 removable 的前 5 个下标 5, 3, 4, 1, 0,把 s 里这几个位置标红,当作已经抹掉。剩下没标红的字符,按原来的顺序还留在 s 里。接着让指针 i 从左往右扫 s,指针 j 指向 p 当前要配的字符,先要配的是 a。只有没被抹掉、又正好等于 p 当前字符的位置,才能把 j 往前推。
- 14开始扫 s。指针 i 走到下标 0,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
- 15指针 i 走到下标 1,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
- 16下标 2 是 c,和 p 当前要配的 a 不一样,配不上,i 右移接着看,j 不动。
- 17指针 i 走到下标 3,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
- 18指针 i 走到下标 4,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
- 19指针 i 走到下标 5,这个位置已经被抹掉了,直接跳过,j 不动,还在等 a。
- 20扫完了,j 只走到 0,还差 a 没配上,p 被抹断了,说明抹 5 个太狠。那 5 以及更多都不行,把右界收到 4,范围变成 3 到 4。继续在更小的个数里试。
- 21第三轮二分。上一轮把范围收到了 [3, 4],取中点得到候选 k 等于 4。同样地问一句:抹掉 removable 前 4 个下标,p 还配得出来吗?
- 22取 removable 的前 4 个下标 5, 3, 4, 1,把 s 里这几个位置标红,当作已经抹掉。剩下没标红的字符,按原来的顺序还留在 s 里。接着让指针 i 从左往右扫 s,指针 j 指向 p 当前要配的字符,先要配的是 a。只有没被抹掉、又正好等于 p 当前字符的位置,才能把 j 往前推。
- 23开始扫 s。下标 0 是 a,正好等于 p 当前要配的 a,配上了,标绿,j 往前推一格,接下来等 b。
- 24指针 i 走到下标 1,这个位置已经被抹掉了,直接跳过,j 不动,还在等 b。
- 25下标 2 是 c,和 p 当前要配的 b 不一样,配不上,i 右移接着看,j 不动。
- 26指针 i 走到下标 3,这个位置已经被抹掉了,直接跳过,j 不动,还在等 b。
- 27指针 i 走到下标 4,这个位置已经被抹掉了,直接跳过,j 不动,还在等 b。
- 28指针 i 走到下标 5,这个位置已经被抹掉了,直接跳过,j 不动,还在等 b。
- 29扫完了,j 只走到 1,还差 b 没配上,p 被抹断了,说明抹 4 个太狠。那 4 以及更多都不行,把右界收到 3,范围变成 3 到 3。左右界撞到一起,二分到此收束。
- 30二分收束了。左界和右界都停在 3,说明 3 是能保住 p 的最多移除个数:抹 3 个时 p 还在,而抹到 4 个就被抹断了。抹掉前 3 个下标 5, 3, 4 后,s 剩下 abc,p 正好配得上。
- 31收个尾。这道题的巧劲在于把「最多能抹几个」这个不好直接求的问题,翻译成「抹 k 个还保不保得住 p」这个好判断的问题,再靠可行性单调二分 k。s 等于 abcabc、p 等于 abc、removable 等于 5,3,4,1,0,2,我们只检验了 3 个候选 k,就锁定最大移除个数是 3。二分把候选个数从线性压成对数级,每次可行性检查线性扫一遍 s,又快又稳。
⚠️ 容易写错的地方
✗ 错：把二分用在 s 的下标上,以为是在 s 里找某个位置
✓ 对：二分的是「移除个数 k 这个答案值」,范围 0 到 removable.length,不是 s 的下标
这是二分答案最核心的转弯。答案的取值有单调可行性,才把二分从「找元素」升级成「找答案分界点」。误当成下标二分会完全跑偏,s 也不需要有序
✗ 错：可行性判定方向搞反,check 成立时反而缩小 k
✓ 对：check(k) 为真(p 仍是子序列)说明还能抹更多,应收左界 lo = mid;为假才收右界 hi = mid - 1
我们要的是最大的可行 k。可行就往大里试、不可行才往小里退。方向反了会收敛到错误的一侧,拿到偏小甚至错误的答案
✗ 错：mid 取法与收界写法不配套,导致死循环
✓ 对：本稿求最大可行值,用 mid 取 lo 加 hi 加 1 再整除 2(偏右取整),配合 lo=mid / hi=mid-1
当只剩两个数、lo=mid 时,若 mid 用普通的 lo 加 hi 整除 2(向下取整)会一直取到 lo 本身、lo 永远不前进,二分卡死。加 1 偏右取整才能保证区间每轮真正缩小
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 lC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int maximumRemovals(string s, string p, vector<int>& removable) {
int m = s.size(), n = p.size();
int l = 0, r = removable.size();
bool rem[m];
auto check = [&](int k) {
memset(rem, false, sizeof(rem));
for (int i = 0; i < k; i++) {
rem[removable[i]] = true;
}
int i = 0, j = 0;
while (i < m && j < n) {
if (!rem[i] && s[i] == p[j]) {
++j;
}
++i;
}
return j == n;
};
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};Java
import java.util.*;
class Solution {
private char[] s;
private char[] p;
private int[] removable;
public int maximumRemovals(String s, String p, int[] removable) {
int l = 0, r = removable.length;
this.s = s.toCharArray();
this.p = p.toCharArray();
this.removable = removable;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
private boolean check(int k) {
boolean[] rem = new boolean[s.length];
for (int i = 0; i < k; ++i) {
rem[removable[i]] = true;
}
int i = 0, j = 0;
while (i < s.length && j < p.length) {
if (!rem[i] && p[j] == s[i]) {
++j;
}
++i;
}
return j == p.length;
}
}复杂度
时间
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),不是常数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 可移除字符的最大数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么移除个数 k 可以拿来二分?单调性体现在哪?+
关键是「抹掉前 k 个下标后 p 还是不是子序列」这个判断关于 k 单调。抹的下标越多,s 里剩下的字符越少,配出 p 只会更难;抹的越少则越容易。于是存在一条分界线,k 小于等于它就保得住、大于它就保不住,不会出现保得住和保不住来回横跳。有了这个单调性,就能像在有序序列里找边界一样二分 k,每次用可行性检查决定往大收还是往小收,把线性枚举压成对数级。
可行性检查里为什么用贪心两指针判子序列就对?+
判断 p 是不是 s 的子序列,标准做法就是贪心:i 扫 s、j 扫 p,一旦遇到没被移除且等于 p 当前字符的位置,就立刻用它去配、把 j 推进。贪心之所以正确,是因为对 p 的当前字符,选最靠左能配上的位置,给后面的字符留下的余地最多,不会比别的选法差。扫完 j 到没到 p 末尾,就决定了可行还是不可行,一遍线性即可。
每次检查都重新扫一遍 s,有没有办法更快?+
这道题数据规模下,朴素的 O(n log m) 已经足够。若要更抠常数,可以反过来预处理:直接算出「p 最后一个被顶掉的时刻」,或者对每个 p 字符维护它在 s 里可用的位置,做到均摊更少的重复扫描。但这类优化会让代码复杂不少,面试里先把二分答案加两指针这套标准解写对写清,再谈优化更稳。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 可移除字符的最大数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。