Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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:
source[1], so that source becomes "a_baa".source[2], so that source 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 * 1031 <= pattern.length <= n1 <= targetIndices.length <= ntargetIndices is sorted in ascending order.targetIndices contains distinct elements in the range [0, n - 1].source and pattern consist only of lowercase English letters.pattern appears as a subsequence in source.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Two Pointers · Dynamic Programming
"abbaa" "aba" [0,1,2]
"bcda" "d" [0,3]
"dda" "dda" [0,1,2]
delete-characters-to-make-fancy-string)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3316: Find Maximum Removals From Source String
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];
}
}
// Accepted solution for LeetCode #3316: Find Maximum Removals From Source String
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]
}
# Accepted solution for LeetCode #3316: Find Maximum Removals From Source String
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]
// Accepted solution for LeetCode #3316: Find Maximum Removals From Source String
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3316: Find Maximum Removals From Source String
// 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];
// }
// }
// Accepted solution for LeetCode #3316: Find Maximum Removals From Source String
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];
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.
Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.