题目描述
给你两个字符串 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
的一个子序列。
字符串的一个 子序列 是一个由原字符串生成的新字符串,生成过程中可能会移除原字符串中的一些字符(也可能不移除)但不改变剩余字符之间的相对顺序。
样例
输入:s = "abcacb", p = "ab", removable = [3,1,0]
输出:2
解释:在移除下标 3 和 1 对应的字符后,"abcacb" 变成 "accb"。
"ab" 是 "accb" 的一个子序列。
如果移除下标 3、1 和 0 对应的字符后,"abcacb" 变成 "ccb",那么 "ab" 就不再是 s 的一个子序列。
因此,最大的 k 是 2。
输入:s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
输出:1
解释:在移除下标 3 对应的字符后,"abcbddddd" 变成 "abcddddd"。
"abcd" 是 "abcddddd" 的一个子序列。
输入: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
中的元素 互不相同。
算法
(二分答案) $O(n \log m)$
- 容易看出,在某个点 $k_0$ 之后,所有的 $k \ge k_0$ 的位置都是不满足条件的,而 $k < k_0$ 都是满足条件的,所以可以二分这个位置。
- 二分找到第一个不满足条件的位。判定时,只需要将不满足条件的字符标记,然后双指针判断是否为子序列。
时间复杂度
- 二分的次数为 $O(\log m)$,每次判定需要 $O(n)$ 的时间,故总时间复杂度为 $O(n \log m)$。其中 $m = removable.length$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储标记数组。
C++ 代码
class Solution {
private:
bool check(const string &s, const string &p, int k, const vector<int> &removable) {
const int n = s.size();
vector<bool> r(n, false);
for (int i = 0; i < k; i++)
r[removable[i]] = true;
int j = 0;
for (int i = 0; i < n && j < p.size(); i++)
if (!r[i] && s[i] == p[j])
j++;
return j == p.size();
}
public:
int maximumRemovals(string s, string p, vector<int>& removable) {
const int m = removable.size();
int l = 0, r = m + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(s, p, mid, removable)) l = mid + 1;
else r = mid;
}
return l - 1;
}
};