Find Maximum Removals From Source String — Solution
Find Maximum Removals From Source String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find Maximum Removals From Source String is a medium coding problem on arrays, strings and hash table, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Dynamic Programming, Two Pointers
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string source of length n, a string pattern that is a subsequence of source, and a sorted array targetIndices of distinct indices in [0, n - 1].
An operation removes the character at some index idx of source, provided that idx is in targetIndices and pattern is still a subsequence of source afterwards. Removing a character does not shift the indices of the other characters.
Return the maximum number of operations that can be performed.
Example 1
Input: source = "abbaa", pattern = "aba", targetIndices = [0,1,2]
Output: 1
Explanation: Removing index 0, 1 or 2 alone keeps "aba" as a subsequence, but removing any two of them breaks it.
Example 2
Input: source = "bcda", pattern = "d", targetIndices = [0,3]
Output: 2
Explanation: Both index 0 ('b') and index 3 ('a') can go; "d" is still there.
Example 3
Input: source = "dda", pattern = "dda", targetIndices = [0,1,2]
Output: 0
Explanation: The pattern is the whole string, so nothing can be removed.
Constraints
1 <= n == source.length <= 3 * 10^31 <= pattern.length <= n1 <= targetIndices.length <= ntargetIndices is sorted in ascending order and its values are distinct0 <= targetIndices[i] <= n - 1source and pattern consist only of lowercase English letterspattern is a subsequence of source
Hints for Find Maximum Removals From Source String
Hint 1
Flip the question: the characters you keep must still contain
patternas a subsequence. Every target index you do not use for matching can be removed.Hint 2
So you want to match
patterninsidesourcewhile using as few target indices as possible. Think of an LCS-style DP over(i, j)= firsticharacters ofsource, firstjofpattern.Hint 3
dp[i][j]= most removable target indices among the firsticharacters while matching the firstjpattern characters: skipsource[i - 1](gain 1 if it is a target) or, if it equalspattern[j - 1], use it for the match.
How to solve Find Maximum Removals From Source String
Removing characters is safe exactly when the remaining characters still embed pattern. So pick one embedding of pattern that touches as few target indices as possible; every other target index can be removed. A subsequence DP finds that embedding.
Approach
- Mark which indices of
sourceare targets. - Let
dp[j]be the maximum number of removable targets so far while having matchedpattern[0..j); start withdp[0] = 0anddp[j] = -∞forj > 0. - For each index
iofsource(witht = 1ifiis a target), updatejfrommdown to 1:dp[j] = max(dp[j] + t, dp[j - 1] if source[i] == pattern[j - 1]); thendp[0] += t. - Return
dp[m].
Why it works
Each character of source is either used to match the next pattern character (so it must stay) or not used (so it may be removed if it is a target, and removing it never hurts). Any set of removals that keeps pattern as a subsequence corresponds to an embedding avoiding the removed indices, and the DP maximises the unused targets over all embeddings.
Complexity
- Time —
O(n · m) - Space —
O(m)
Pitfalls
- Updating
jupwards would let one character match two pattern positions — go frommdown to 1. - Greedily matching
patternas early as possible is wrong: it may use target indices that a later match would have avoided.
Reference solution
Python
from typing import List
def maxRemovals(source: str, pattern: str, targetIndices: List[int]) -> int:
n, m = len(source), len(pattern)
is_target = [0] * n
for i in targetIndices:
is_target[i] = 1
NEG = -10**9
dp = [0] + [NEG] * m
for i in range(n):
t = is_target[i]
c = source[i]
for j in range(m, 0, -1):
best = dp[j] + t
if c == pattern[j - 1] and dp[j - 1] > best:
best = dp[j - 1]
dp[j] = best
dp[0] += t
return dp[m]Java
public static int maxRemovals(String source, String pattern, int[] targetIndices) {
int n = source.length(), m = pattern.length();
int[] isTarget = new int[n];
for (int i : targetIndices) isTarget[i] = 1;
final int NEG = -1000000000;
int[] dp = new int[m + 1];
Arrays.fill(dp, NEG);
dp[0] = 0;
for (int i = 0; i < n; i++) {
int t = isTarget[i];
char c = source.charAt(i);
for (int j = m; j >= 1; j--) {
int best = dp[j] + t;
if (c == pattern.charAt(j - 1) && dp[j - 1] > best) best = dp[j - 1];
dp[j] = best;
}
dp[0] += t;
}
return dp[m];
}C++
int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
int n = source.size(), m = pattern.size();
vector<int> isTarget(n, 0);
for (int i : targetIndices) isTarget[i] = 1;
const int NEG = -1000000000;
vector<int> dp(m + 1, NEG);
dp[0] = 0;
for (int i = 0; i < n; i++) {
int t = isTarget[i];
for (int j = m; j >= 1; j--) {
int best = dp[j] + t;
if (source[i] == pattern[j - 1] && dp[j - 1] > best) best = dp[j - 1];
dp[j] = best;
}
dp[0] += t;
}
return dp[m];
}JavaScript
var maxRemovals = function(source, pattern, targetIndices) {
var n = source.length, m = pattern.length;
var isTarget = new Array(n).fill(0);
for (var a = 0; a < targetIndices.length; a++) isTarget[targetIndices[a]] = 1;
var NEG = -1000000000;
var dp = [0];
for (var j = 1; j <= m; j++) dp.push(NEG);
for (var i = 0; i < n; i++) {
var t = isTarget[i], c = source.charAt(i);
for (var k = m; k >= 1; k--) {
var best = dp[k] + t;
if (c === pattern.charAt(k - 1) && dp[k - 1] > best) best = dp[k - 1];
dp[k] = best;
}
dp[0] += t;
}
return dp[m];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.