3316. Find Maximum Removals From Source String LeetCode Solution
In this guide, you will get 3316. Find Maximum Removals From Source String LeetCode Solution with the best time and space complexity. The solution to Find Maximum Removals From Source String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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:
idx is an element of targetIndices.
pattern remains a subsequence of source 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 that source becomes “a_baa”.
Remove source[2], so that source becomes “ab_aa”.
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 and pattern consist only of lowercase English letters.
The input is generated such that pattern appears as a subsequence in source.
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
3316. Find Maximum Removals From Source String LeetCode Solution in C++
class Solution {
public:
int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
const unordered_set<int> target{targetIndices.begin(), targetIndices.end()};
vector<vector<int>> mem(source.length(), vector<int>(pattern.length(), -1));
const int ans = maxRemovals(source, pattern, 0, 0, target, mem);
return ans == INT_MIN ? 0 : ans;
}
private:
// Returns the maximum number of operations that can be performed for
// source[i..m) and pattern[j..n).
int maxRemovals(const string& source, const string& pattern, int i, int j,
const unordered_set<int>& target, vector<vector<int>>& mem) {
if (i == source.length())
return j == pattern.length() ? 0 : INT_MIN;
if (j == pattern.length())
return (target.contains(i) ? 1 : 0) +
maxRemovals(source, pattern, i + 1, j, target, mem);
if (mem[i][j] != -1)
return mem[i][j];
const int pick =
source[i] == pattern[j]
? maxRemovals(source, pattern, i + 1, j + 1, target, mem)
: INT_MIN;
const int skip = (target.contains(i) ? 1 : 0) +
maxRemovals(source, pattern, i + 1, j, target, mem);
return mem[i][j] = max(pick, skip);
};
}; /* code provided by PROGIEZ */
3316. Find Maximum Removals From Source String LeetCode Solution in Java
class Solution {
public int maxRemovals(String source, String pattern, int[] targetIndices) {
Set<Integer> target = Arrays.stream(targetIndices).boxed().collect(Collectors.toSet());
Integer[][] mem = new Integer[source.length()][pattern.length()];
final int ans = maxRemovals(source, pattern, 0, 0, target, mem);
return ans == Integer.MIN_VALUE ? 0 : ans;
}
// Returns the maximum number of operations that can be performed for
// source[i..m) and pattern[j..n).
private int maxRemovals(String source, String pattern, int i, int j, Set<Integer> target,
Integer[][] mem) {
if (i == source.length())
return j == pattern.length() ? 0 : Integer.MIN_VALUE;
if (j == pattern.length())
return (target.contains(i) ? 1 : 0) + maxRemovals(source, pattern, i + 1, j, target, mem);
if (mem[i][j] != null)
return mem[i][j];
final int pick = source.charAt(i) == pattern.charAt(j)
? maxRemovals(source, pattern, i + 1, j + 1, target, mem)
: Integer.MIN_VALUE;
final int skip =
(target.contains(i) ? 1 : 0) + maxRemovals(source, pattern, i + 1, j, target, mem);
return mem[i][j] = Math.max(pick, skip);
}
} // code provided by PROGIEZ
3316. Find Maximum Removals From Source String LeetCode Solution in Python
class Solution:
def maxRemovals(
self,
source: str,
pattern: str,
targetIndices: list[int]
) -> int:
m = len(source)
n = len(pattern)
target = set(targetIndices)
@functools.lru_cache(None)
def dp(i: int, j: int) -> int:
"""
Returns the maximum number of operations that can be performed for
source[i..m) and pattern[j..n).
"""
if i == m:
return 0 if j == n else -math.inf
if j == n:
return int(i in target) + dp(i + 1, j)
pick = dp(i + 1, j + 1) if source[i] == pattern[j] else -math.inf
skip = int(i in target) + dp(i + 1, j)
return max(pick, skip)
ans = dp(0, 0)
return 0 if ans == -math.inf else ans # code by PROGIEZ
