可移除字符的最大数目 图解题解

抹掉一批下标还想保住 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 偏右取整。

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 l

C++

#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;
    }
}