可移除字符的最大数目

难度: Medium

给你两个字符串 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 中的元素 互不相同

Submission

运行时间: 649 ms

内存: 26.3 MB

class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        # 二分查找
        left = 0
        right = len(removable) + 1
        n = len(p)
        while right > left:
            mid = left + right >> 1
            l = list(s)
            for i in range(mid):
                l[removable[i]] = ''
            s2 = ''.join(l)
            i = 0
            for c in s2:
                if c == p[i]:
                    i += 1
                    if i == n:
                        left = mid + 1
                        break
            else:
                right = mid
        return left - 1

Explain

本题解采用二分查找来确定最大的 k 值。我们定义两个边界：left 和 right，初始化 left 为 0，right 为 removable.length + 1。我们在这个范围内进行二分搜索，检查每一个中间值 mid。对于每个 mid，我们尝试从字符串 s 中移除前 mid 个在 removable 数组中指定的字符。移除后，我们检查 p 是否仍然是新字符串的子序列。如果是，我们将搜索范围的左边界移动到 mid + 1；如果不是，我们将右边界设置为 mid。继续这个过程，直到 left 和 right 相遇。最终，left - 1 将是满足条件的最大 k 值。

时间复杂度: O(removable.length * s.length * log(removable.length))

空间复杂度: O(s.length)

class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        left = 0  # 初始化二分搜索的左边界
        right = len(removable) + 1  # 初始化二分搜索的右边界
        n = len(p)  # p 的长度
        while right > left:  # 当左边界小于右边界时循环
            mid = (left + right) >> 1  # 计算中间值
            l = list(s)  # 将字符串 s 转换为列表，便于修改
            for i in range(mid):  # 移除前 mid 个字符
                l[removable[i]] = ''
            s2 = ''.join(l)  # 生成新的字符串
            i = 0  # 用于检查 p 是否为 s2 的子序列
            for c in s2:
                if c == p[i]:  # 如果字符匹配，移动 p 中的指针
                    i += 1
                    if i == n:  # 如果 p 被完全匹配，将左边界移至 mid + 1
                        left = mid + 1
                        break
            else:  # 如果循环完成未完全匹配 p，将右边界设置为 mid
                right = mid
        return left - 1  # 返回最大的 k 值，即 left - 1

Explore

在二分查找中，设置`right`为`removable.length + 1`是为了包含全部移除`removable`数组中所有元素的情况。二分查找的过程中，通常`right`是不被包括在搜索区间中的。如果设置`right`为`removable.length`，那么最大的`mid`值将是`removable.length - 1`，这意味着最后一个元素永远不会被考虑是否可以移除。通过设置`right`为`removable.length + 1`，可以确保在二分搜索时能够测试到所有可能的移除数量，从0到`removable.length`个元素都能被考虑。

是的，可以优化这个检查过程。一种方法是使用一个布尔数组来标记哪些字符被移除，而不是真的从字符串中删除字符并重新组合。这样，我们可以在不修改原字符串的情况下，直接通过跳过被标记为移除的字符来检查`p`是否为子序列，这将显著减少字符串操作的开销。另一种可能的优化是使用动态规划或者其他高级数据结构（如线段树或树状数组）来更快地检查子序列的存在性。

直接修改字符串并重新检查子序列的方法虽然可行，但不是最优。这种方法涉及频繁的字符串操作，可能导致较高的时间复杂度。更优的策略可能包括使用额外的数据结构来避免字符串的频繁修改。例如，可以使用布尔数组或位向量来追踪哪些字符被移除，然后通过忽略这些字符来检查子序列。这减少了字符串操作的需要，可以更快地执行。

返回`left - 1`通常是正确的，因为在二分查找的过程中，当`mid`使`p`不再是子序列时，`right`会设置为`mid`，这意味着最后一次`p`作为子序列成功的`mid`值实际上是`left - 1`。然而，在极端情况下，如果`p`一开始就不是`s`的子序列，或者没有任何移除操作可以使`p`成为子序列，那么最终的`left`可能会是0，此时`left - 1`会返回-1，这在逻辑上是不正确的。因此，在实际应用中可能需要在返回前加入检查，确保返回值非负。