Medium

题目描述

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

请你找出一个整数 k（0 <= k <= removable.length），选出 removable 中的 前 k 个下标，然后从 s 中移除这些下标对应的 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^5
  • 0 <= removable.length < s.length
  • 0 <= removable[i] < s.length
  • p 是 s 的一个子序列
  • s 和 p 仅由小写英文字母组成
  • removable 中的元素互不相同

解题思路

这道题的核心思路是使用二分搜索来寻找最大的可移除字符数量。

首先分析问题：我们需要找到最大的 k，使得从 s 中移除 removable 数组前 k 个位置的字符后，p 仍然是 s 的子序列。

关键观察：

  1. 如果移除前 k 个字符后 p 仍是子序列，那么移除前 k-1 个字符后 p 也一定是子序列
  2. 如果移除前 k 个字符后 p 不是子序列，那么移除前 k+1 个字符后 p 也一定不是子序列

这种单调性特点使得我们可以使用二分搜索来优化求解。

解题步骤：

  1. 设定二分搜索的边界：left = 0, right = removable.length
  2. 对于每个中间值 mid，检查移除前 mid 个字符后 p 是否仍是 s 的子序列
  3. 检查子序列的方法：使用双指针技术，跳过被标记为移除的字符位置
  4. 根据检查结果调整搜索范围

子序列检查函数：

  • 使用集合存储需要移除的字符位置
  • 用两个指针分别遍历字符串 s 和 p
  • 如果当前 s 的位置不在移除集合中且字符匹配，则两个指针都向前移动
  • 否则只移动 s 的指针

代码实现

class Solution {
public:
    bool isSubsequence(const string& s, const string& p, const unordered_set<int>& removed) {
        int i = 0, j = 0;
        while (i < s.length() && j < p.length()) {
            if (removed.find(i) == removed.end() && s[i] == p[j]) {
                j++;
            }
            i++;
        }
        return j == p.length();
    }
    
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int left = 0, right = removable.size();
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            unordered_set<int> removed;
            
            for (int i = 0; i < mid; i++) {
                removed.insert(removable[i]);
            }
            
            if (isSubsequence(s, p, removed)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        def isSubsequence(s, p, removed_set):
            i = j = 0
            while i < len(s) and j < len(p):
                if i not in removed_set and s[i] == p[j]:
                    j += 1
                i += 1
            return j == len(p)
        
        left, right = 0, len(removable)
        result = 0
        
        while left <= right:
            mid = (left + right) // 2
            removed_set = set(removable[:mid])
            
            if isSubsequence(s, p, removed_set):
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class Solution {
    private bool IsSubsequence(string s, string p, HashSet<int> removed) {
        int i = 0, j = 0;
        while (i < s.Length && j < p.Length) {
            if (!removed.Contains(i) && s[i] == p[j]) {
                j++;
            }
            i++;
        }
        return j == p.Length;
    }
    
    public int MaximumRemovals(string s, string p, int[] removable) {
        int left = 0, right = removable.Length;
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            HashSet<int> removed = new HashSet<int>();
            
            for (int i = 0; i < mid; i++) {
                removed.Add(removable[i]);
            }
            
            if (IsSubsequence(s, p, removed)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
}

var maximumRemovals = function(s, p, removable) {
    function isSubsequence(s, p, removed) {
        let i = 0, j = 0;
        while (i < s.length && j < p.length) {
            if (!removed.has(i) && s[i] === p[j]) {
                j++;
            }
            i++;
        }
        return j === p.length;
    }
    
    let left = 0, right = removable.length;
    let result = 0;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let removed = new Set(removable.slice(0, mid));
        
        if (isSubsequence(s, p, removed)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(k × log k × (m + n))，其中 k = removable.length，m = s.length，n = p.length
空间复杂度O(k)，用于存储移除位置的集合

相关题目