3316. Find Maximum Removals From Source String
Description
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:
idx
is an element oftargetIndices
.pattern
remains a subsequence ofsource
after 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: 1
Explanation:
We can't remove source[0]
but we can do either of these two operations:
- Remove
source[1]
, so thatsource
becomes"a_baa"
. - Remove
source[2]
, so thatsource
becomes"ab_aa"
.
Example 2:
Input: source = "bcda", pattern = "d", targetIndices = [0,3]
Output: 2
Explanation:
We can remove source[0]
and source[3]
in two operations.
Example 3:
Input: source = "dda", pattern = "dda", targetIndices = [0,1,2]
Output: 0
Explanation:
We can't remove any character from source
.
Example 4:
Input: source = "yeyeykyded", pattern = "yeyyd", targetIndices = [0,2,3,4]
Output: 2
Explanation:
We can remove source[2]
and source[3]
in two operations.
Constraints:
1 <= n == source.length <= 3 * 103
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
andpattern
consist only of lowercase English letters.- The input is generated such that
pattern
appears as a subsequence insource
.
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ to represent the maximum number of deletions in the first $i$ characters of $\textit{source}$ that match the first $j$ characters of $\textit{pattern}$. Initially, $f[0][0] = 0$, and the rest $f[i][j] = -\infty$.
For $f[i][j]$, we have two choices:
- We can skip the $i$-th character of $\textit{source}$, in which case $f[i][j] = f[i-1][j] + \text{int}(i-1 \in \textit{targetIndices})$;
- If $\textit{source}[i-1] = \textit{pattern}[j-1]$, we can match the $i$-th character of $\textit{source}$, in which case $f[i][j] = \max(f[i][j], f[i-1][j-1])$.
The final answer is $f[m][n]$.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the lengths of $\textit{source}$ and $\textit{pattern}$, respectively.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
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 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|