Find Maximum Removals From Source String
You are given a string source of size n, a string pattern that is a subsequence of source, and a sorted integer array targetIndices that contains distinct numbers in the range [0, n - 1].
We define an operation as removing a character at an index idx from source such that:
idxis an element oftargetIndices.patternremains a subsequence ofsourceafter removing the character.
Performing an operation does not change the indices of the other characters in source. For example, if you remove 'c' from "acb", the character at index 2 would still be 'b'.
Return the maximum number of operations that can be performed.
Example 1
Input
source = "abbaa", pattern = "aba", targetIndices = [0,1,2]Output
1We can't remove
source[0], but we can remove either source[1] or source[2] while keeping pattern as a subsequence.Example 2
Input
source = "bcda", pattern = "d", targetIndices = [0,3]Output
2We can remove
source[0] and source[3] in two operations.Constraints
- 1 <= n == source.length <= 3 * 10^3
- 1 <= pattern.length <= n
- 1 <= targetIndices.length <= n
- targetIndices is sorted in ascending order.
- The input is generated such that targetIndices contains distinct elements in the range [0, n - 1].
- source and pattern consist only of lowercase English letters.
- The input is generated such that pattern appears as a subsequence in source.