Welcome to Subscribe On Youtube
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.
-
class Solution { public int maxRemovals(String source, String pattern, int[] targetIndices) { int m = source.length(), n = pattern.length(); int[][] f = new int[m + 1][n + 1]; final int inf = Integer.MAX_VALUE / 2; for (var g : f) { Arrays.fill(g, -inf); } f[0][0] = 0; int[] s = new int[m]; for (int i : targetIndices) { s[i] = 1; } for (int i = 1; i <= m; ++i) { for (int j = 0; j <= n; ++j) { f[i][j] = f[i - 1][j] + s[i - 1]; if (j > 0 && source.charAt(i - 1) == pattern.charAt(j - 1)) { f[i][j] = Math.max(f[i][j], f[i - 1][j - 1]); } } } return f[m][n]; } }
-
class Solution { public: int maxRemovals(string source, string pattern, vector<int>& targetIndices) { int m = source.length(), n = pattern.length(); vector<vector<int>> f(m + 1, vector<int>(n + 1, INT_MIN / 2)); f[0][0] = 0; vector<int> s(m); for (int i : targetIndices) { s[i] = 1; } for (int i = 1; i <= m; ++i) { for (int j = 0; j <= n; ++j) { f[i][j] = f[i - 1][j] + s[i - 1]; if (j > 0 && source[i - 1] == pattern[j - 1]) { f[i][j] = max(f[i][j], f[i - 1][j - 1]); } } } return f[m][n]; } };
-
class Solution: def maxRemovals(self, source: str, pattern: str, targetIndices: List[int]) -> int: m, n = len(source), len(pattern) f = [[-inf] * (n + 1) for _ in range(m + 1)] f[0][0] = 0 s = set(targetIndices) for i, c in enumerate(source, 1): for j in range(n + 1): f[i][j] = f[i - 1][j] + int((i - 1) in s) if j and c == pattern[j - 1]: f[i][j] = max(f[i][j], f[i - 1][j - 1]) return f[m][n]
-
func maxRemovals(source string, pattern string, targetIndices []int) int { m, n := len(source), len(pattern) f := make([][]int, m+1) for i := range f { f[i] = make([]int, n+1) for j := range f[i] { f[i][j] = -math.MaxInt32 / 2 } } f[0][0] = 0 s := make([]int, m) for _, i := range targetIndices { s[i] = 1 } for i := 1; i <= m; i++ { for j := 0; j <= n; j++ { f[i][j] = f[i-1][j] + s[i-1] if j > 0 && source[i-1] == pattern[j-1] { f[i][j] = max(f[i][j], f[i-1][j-1]) } } } return f[m][n] }
-
function maxRemovals(source: string, pattern: string, targetIndices: number[]): number { const m = source.length; const n = pattern.length; const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(-Infinity)); f[0][0] = 0; const s = Array(m).fill(0); for (const i of targetIndices) { s[i] = 1; } for (let i = 1; i <= m; i++) { for (let j = 0; j <= n; j++) { f[i][j] = f[i - 1][j] + s[i - 1]; if (j > 0 && source[i - 1] === pattern[j - 1]) { f[i][j] = Math.max(f[i][j], f[i - 1][j - 1]); } } } return f[m][n]; }