You are given two strings s
and p
where p
is a subsequence of s
. You are also given a distinct 0-indexed integer array removable
containing a subset of indices of s
(s
is also 0-indexed).
You want to choose an integer k
(0 <= k <= removable.length
) such that, after removing k
characters from s
using the first k
indices in removable
, p
is still a subsequence of s
. More formally, you will mark the character at s[removable[i]]
for each 0 <= i < k
, then remove all marked characters and check if p
is still a subsequence.
Return the maximum k
you can choose such that p
is still a subsequence of s
after the removals.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
Example 1:
Input: s = "abcacb", p = "ab", removable = [3,1,0] Output: 2 Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb". "ab" is a subsequence of "accb". If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence. Hence, the maximum k is 2.
Example 2:
Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6] Output: 1 Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd". "abcd" is a subsequence of "abcddddd".
Example 3:
Input: s = "abcab", p = "abc", removable = [0,1,2,3,4] Output: 0 Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.
Constraints:
1 <= p.length <= s.length <= 105
0 <= removable.length < s.length
0 <= removable[i] < s.length
p
is a subsequence ofs
.s
andp
both consist of lowercase English letters.- The elements in
removable
are distinct.
Solution: Binary Search + Two Pointers
If we don’t remove any thing, p is a subseq of s, as we keep removing, at some point L, p is no longer a subseq of s. e.g [0:True, 1: True, …, L – 1: True, L: False, L+1: False, …, m:False], this array is monotonic. We can use binary search to find the smallest L such that p is no long a subseq of s. Ans = L – 1.
For each guess, we can use two pointers to check whether p is subseq of removed(s) in O(n).
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua class Solution { public: int maximumRemovals(string s, string p, vector<int>& removable) { const int n = s.length(); const int t = p.length(); const int m = removable.size(); int l = 0; int r = m + 1; vector<int> idx(n, INT_MAX); for (int i = 0; i < m; ++i) idx[removable[i]] = i; while (l < r) { int mid = l + (r - l) / 2; int j = 0; for (int i = 0; i < n && j < t; ++i) if (idx[i] >= mid && s[i] == p[j]) ++j; if (j != t) r = mid; else l = mid + 1; } // l is the smallest number s.t. p is no longer a subseq of s. return l - 1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment