Why is binary search valid for Maximum Number of Removable Characters?

Because the answer space is monotonic. If p is still a subsequence after removing the first k indices, then it will also be a subsequence for every smaller k. Once a value fails, every larger value fails as well.

How do you check whether p is still a subsequence after k removals?

Mark the first k indices from removable as deleted. Then scan s with one pointer and p with another. Skip deleted positions in s, match characters in order, and succeed only if the p pointer reaches the end.

Why not physically remove characters from s each time?

Building a new string for every binary search step adds overhead and is unnecessary. This problem only needs to know whether a position is usable during the subsequence scan, so a removed marker array is simpler and faster.

What is the main failure mode in this problem?

The subsequence check fails when deletions remove too many useful positions from s, so the two-pointer scan can no longer match all characters of p in order. That is the exact boundary binary search is trying to find.

What pattern should I remember from this problem title?

Remember binary search over the valid answer space combined with a linear feasibility check. In Maximum Number of Removable Characters, the feasibility check is a subsequence test after marking the first k removable indices.

#1898

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

可移除字符的最大数目

给你两个字符串 s 和 p ，其中 p 是 s 的一个子序列。同时，给你一个元素互不相同且下标从 0 开始计数的整数数组 removable ，该数组是 s 中下标的一个子集（ s 的下标也从 0 开始计数）。请你找出一个整数 k （ 0 ），选出 removable 中的前 k…

数组双指针字符串二分查找

题目描述

给你两个字符串 s 和 p ，其中 p 是 s 的一个 子序列 。同时，给你一个元素 互不相同 且下标 从 0 开始 计数的整数数组 removable ，该数组是 s 中下标的一个子集（s 的下标也 从 0 开始 计数）。

请你找出一个整数 k（0 <= k <= removable.length），选出 removable 中的前 k 个下标，然后从 s 中移除这些下标对应的 k 个字符。整数 k 需满足：在执行完上述步骤后， p 仍然是 s 的一个 子序列 。更正式的解释是，对于每个 0 <= i < k ，先标记出位于 s[removable[i]] 的字符，接着移除所有标记过的字符，然后检查 p 是否仍然是 s 的一个子序列。

返回你可以找出的最大 k ，满足在移除字符后 p 仍然是 s 的一个子序列。

字符串的一个 子序列 是一个由原字符串生成的新字符串，生成过程中可能会移除原字符串中的一些字符（也可能不移除）但不改变剩余字符之间的相对顺序。

示例 1：

输入：s = "abcacb", p = "ab", removable = [3,1,0]
输出：2
解释：在移除下标 3 和 1 对应的字符后，"abcacb" 变成 "accb" 。
"ab" 是 "accb" 的一个子序列。
如果移除下标 3、1 和 0 对应的字符后，"abcacb" 变成 "ccb" ，那么 "ab" 就不再是 s 的一个子序列。
因此，最大的 k 是 2 。

示例 2：

输入：s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
输出：1
解释：在移除下标 3 对应的字符后，"abcbddddd" 变成 "abcddddd" 。
"abcd" 是 "abcddddd" 的一个子序列。

示例 3：

输入：s = "abcab", p = "abc", removable = [0,1,2,3,4]
输出：0
解释：如果移除数组 removable 的第一个下标，"abc" 就不再是 s 的一个子序列。

提示：

1 <= p.length <= s.length <= 10⁵
0 <= removable.length < s.length
0 <= removable[i] < s.length
p 是 s 的一个 子字符串
s 和 p 都由小写英文字母组成
removable 中的元素 互不相同

lightbulb

解题思路

方法一：二分查找

我们注意到，如果移除 $\textit{removable}$ 前 $k$ 个下标对应的字符后，满足 $p$ 仍然是 $s$ 的一个子序列，那么移除 $k \lt k' \leq \textit{removable.length}$ 个下标对应的字符后，依然满足条件，这存在着单调性。因此，我们可以使用二分查找，找到最大的 $k$ 。

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = \textit{removable.length}$ ，然后进行二分查找。在每次查找中，我们取中间值 $mid = \left\lfloor \frac{l + r + 1}{2} \right\rfloor$ ，然后检查移除 $\textit{removable}$ 的前 $mid$ 个下标对应的字符后，是否满足 $p$ 仍然是 $s$ 的一个子序列。如果满足，我们更新左边界 $l = mid$ ，否则更新右边界 $r = mid - 1$ 。

二分查找结束后，返回左边界 $l$ 即可。

时间复杂度 $O(k \times \log k)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串 $s$ 的长度，而 $k$ 是 $\textit{removable}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They expect you to notice monotonicity in the answer, not binary search on string positions.
question_mark
They want a subsequence checker that skips removed indices without physically rebuilding s.
question_mark
They are testing whether you can separate the search over k from the validation logic.

warning

常见陷阱

外企场景

error
Rebuilding the filtered string on every check adds unnecessary overhead and obscures the two-pointer logic.
error
Using binary search without proving why a larger removable prefix cannot recover once a smaller one already fails.
error
Forgetting that only the first k indices in removable count, not any arbitrary set of k deletions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the minimum k that makes p stop being a subsequence instead of the maximum k that keeps it valid.
arrow_right_alt
Allow multiple queries with different p values, which pushes you to rethink repeated subsequence checks.
arrow_right_alt
Replace subsequence matching with substring matching, which breaks the simple two-pointer validation used here.

help

常见问题

外企场景

继续练习

#1855 下标对中的最大距离 #1961 检查字符串是否为数组前缀 #1813 句子相似性 III