Find Maximum Removals From Source String solution and explanation
Google
7 more videos on this problem
Leetcode Biweekly Contest 141 | 3316. Find Maximum Removals From Source String | DP | CodefodCodeFod · 14:52 · 1K views
Find Maximum Removals From Source String || LeetCode Biweekly Contest 141 || Leetcode Solutioncodi · 0:58 · 1K views
3316. Find Maximum Removals From Source String (Leetcode Medium)Programming Live with Larry · 30:41 · 685 views
Leetcode 3316 | Find Maximum Removals From Source String | Biweekly Contest 141Road To FAANG · 11:06 · 662 views
3316. Find Maximum Removals From Source String || Leetcode Biweekly 141 || #leetcode #dsaGad-An-Tik · 10:44 · 380 views
Biweekly Contest | First 3 Problems- 3314, 3315 & 3316 | LeetcodeAmit Choraria · 24:17 · 200 views
LeetCode 3316 - Find Maximum Removals From Source String - PythonAlpha-Code · 13:57 · 106 views
Leetcode 3316. Find Maximum Removals From Source String (lcs)LetsCode · 19:57 · 27 views
The problem
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:
idxis an element oftargetIndices.patternremains a subsequence ofsourceafter 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 thatsourcebecomes"a_baa". - Remove
source[2], so thatsourcebecomes"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 <= ntargetIndicesis sorted in ascending order.- The input is generated such that
targetIndicescontains distinct elements in the range[0, n - 1]. sourceandpatternconsist only of lowercase English letters.- The input is generated such that
patternappears as a subsequence insource.
Approach overview
Problem Overview: You are given a source string s, a pattern p, and a list of removable indices. Remove characters from s in the given order while keeping p a subsequence. The goal is to compute the maximum number of removals that still preserves the subsequence relationship.
Approach 1: Binary Search with Subsequence Validation (O(n log k) time, O(n) space)
The key observation: if removing k characters still keeps p as a subsequence, then removing fewer than k will also work. That monotonic property allows binary search on the number of removals. For a candidate value mid, mark the first mid indices as removed and scan the string using a two pointer subsequence check. One pointer walks through s, the other through p, skipping removed characters. If the pattern pointer reaches the end, the subsequence still exists. Adjust the binary search range accordingly. Each validation pass takes O(n), and binary search runs O(log k) times where k is the number of removable indices.
Approach 2: Two Pointer Greedy Simulation (O(n + k) time, O(n) space)
This approach simulates the removals directly while maintaining the subsequence check with two pointers. Use a boolean array to track removed positions in s. Iterate through the removal order and update the removed state. After each update, scan s using two pointers to verify whether p is still a subsequence. The pointer for s advances across the string while skipping removed indices, and the pointer for p advances only when characters match. The process stops when the subsequence condition breaks. The last valid removal count is the answer. The logic relies heavily on string traversal and pointer movement.
Recommended for interviews: Binary Search with Subsequence Validation is the approach most interviewers expect. It demonstrates recognition of a monotonic condition and combines binary search with a classic two‑pointer subsequence check. The greedy simulation helps build intuition, but the binary search solution shows stronger algorithmic thinking and handles larger inputs efficiently.
Approach 1: Binary Search with Subsequence Validation
This approach involves using binary search on the number of possible removals and validating whether the 'pattern' is still a subsequence after a certain number of removals. It leverages the fact that if 'pattern' is a subsequence after some removals, it will also be a subsequence with fewer removals.
def is_subsequence(source, pattern, remove, k):
removed = [False] * len(source)
for i in range(k):
removed[remove[i]] = True
j = 0
for i in range(len(source)):
if not removed[i] and j < len(pattern) and source[i] == pattern[j]:
j += 1
return j == len(pattern)
def max_removals(source, pattern, target_indices):
left, right = 0, len(target_indices)
while left < right:
mid = (left + right + 1) // 2
if is_subsequence(source, pattern, target_indices, mid):
left = mid
else:
right = mid - 1
return leftpublic class MaxRemovals {
public static boolean isSubsequence(String source, String pattern, int[] remove, int k) {
boolean[] removed = new boolean[source.length()];
for (int i = 0; i < k; i++) {
removed[remove[i]] = true;
}
int j = 0;
for (int i = 0; i < source.length() && j < pattern.length(); i++) {
if (!removed[i] && source.charAt(i) == pattern.charAt(j)) {
j++;
}
}
return j == pattern.length();
}
public static int maxRemovals(String source, String pattern, int[] targetIndices) {
int left = 0, right = targetIndices.length;
while (left < right) {
int mid = (left + right + 1) / 2;
if (isSubsequence(source, pattern, targetIndices, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}#include <vector>
#include <string>
using namespace std;
bool isSubsequence(const string& source, const string& pattern, const vector<int>& remove, int k) {
vector<bool> removed(source.size(), false);
for (int i = 0; i < k; ++i) {
removed[remove[i]] = true;
}
int j = 0;
for (int i = 0; i < source.size() && j < pattern.size(); ++i) {
if (!removed[i] && source[i] == pattern[j]) {
++j;
}
}
return j == pattern.size();
}
int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
int left = 0, right = targetIndices.size();
while (left < right) {
int mid = (left + right + 1) / 2;
if (isSubsequence(source, pattern, targetIndices, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}function isSubsequence(source, pattern, remove, k) {
const removed = Array(source.length).fill(false);
for (let i = 0; i < k; i++) {
removed[remove[i]] = true;
}
let j = 0;
for (let i = 0; i < source.length && j < pattern.length; i++) {
if (!removed[i] && source[i] === pattern[j]) {
j++;
}
}
return j === pattern.length;
}
function maxRemovals(source, pattern, targetIndices) {
let left = 0, right = targetIndices.length;
while (left < right) {
const mid = Math.floor((left + right + 1) / 2);
if (isSubsequence(source, pattern, targetIndices, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}#include <stdbool.h>
#include <string.h>
bool isSubsequence(char* source, char* pattern, int* remove, int k, int n) {
bool removed[n];
memset(removed, false, sizeof(removed));
for (int i = 0; i < k; i++)
removed[remove[i]] = true;
int j = 0;
for (int i = 0; i < n && j < strlen(pattern); i++) {
if (!removed[i] && source[i] == pattern[j]) {
j++;
}
}
return j == strlen(pattern);
}
int maxRemovals(char* source, char* pattern, int* targetIndices, int targetSize) {
int left = 0, right = targetSize;
int n = strlen(source);
while (left < right) {
int mid = (left + right + 1) / 2;
if (isSubsequence(source, pattern, targetIndices, mid, n)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}using System;
public class Solution {
public bool IsSubsequence(string source, string pattern, int[] remove, int k) {
bool[] removed = new bool[source.Length];
for (int i = 0; i < k; i++) {
removed[remove[i]] = true;
}
int j = 0;
for (int i = 0; i < source.Length && j < pattern.Length; i++) {
if (!removed[i] && source[i] == pattern[j]) {
j++;
}
}
return j == pattern.Length;
}
public int MaxRemovals(string source, string pattern, int[] targetIndices) {
int left = 0, right = targetIndices.Length;
while (left < right) {
int mid = (left + right + 1) / 2;
if (IsSubsequence(source, pattern, targetIndices, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}Python solution uses a binary search to optimize the number of removable characters from the source while maintaining the pattern as a subsequence. The helper function is used to simulate the removal of the first 'k' target indices and checks subsequence condition.
Time Complexity: O(n * log(m)); n being the length of 'source' and m the length of targetIndices.
Space Complexity: O(n), for the removed list.
Approach 2: Two Pointer Greedy Approach
This technique uses a two-pointer approach to iteratively check and remove as long as 'pattern' remains a subsequence.
def max_removals_two_pointer(source, pattern, target_indices):
max_removals = 0
j = 0
m = len(pattern)
n = len(source)
for k in target_indices:
while j < n and j <= k:
if source[j] == pattern[max_removals]:
max_removals += 1
j += 1
if max_removals == m:
return max_removals - 1
return max_removalspublic class MaxRemovals {
public static int maxRemovalsTwoPointer(String source, String pattern, int[] targetIndices) {
int maxRemovals = 0;
int j = 0, m = pattern.length();
for (int x = 0, i = 0; i < targetIndices.length && j != m; ++i) {
int k = targetIndices[i];
while (x <= k && j < m) {
if (source.charAt(x++) == pattern.charAt(j)) j++;
}
if (j == m) break;
maxRemovals++;
}
return maxRemovals;
}
}#include <vector>
#include <string>
using namespace std;
int maxRemovalsTwoPointer(string source, string pattern, vector<int>& targetIndices) {
int maxRemovals = 0;
int j = 0, m = pattern.size();
for (int i = 0; i < targetIndices.size() && j != m; ++i) {
int k = targetIndices[i];
for (int x = 0; x <= k && j < m; ++x) {
if (source[x] == pattern[j]) j++;
}
if (j == m) break;
maxRemovals++;
}
return maxRemovals;
}function maxRemovalsTwoPointer(source, pattern, targetIndices) {
let maxRemovals = 0;
let j = 0, m = pattern.length;
for (let x = 0, i = 0; i < targetIndices.length && j !== m; i++) {
let k = targetIndices[i];
while (x <= k && j < m) {
if (source[x++] === pattern[j]) j++;
}
if (j === m) break;
maxRemovals++;
}
return maxRemovals;
}#include <stdbool.h>
#include <string.h>
int maxRemovalsTwoPointer(char* source, char* pattern, int* targetIndices, int targetSize) {
int maxRemovals = 0;
int j = 0, m = strlen(pattern);
for (int i = 0; i < targetSize; ++i) {
int k = targetIndices[i];
// Check if removing affects pattern forming
for (int x = 0; x <= k && j < m; ++x) {
if (source[x] == pattern[j]) j++;
}
if (j == m) break;
maxRemovals++;
}
return maxRemovals;
}public class MaxRemovals {
public int MaxRemovalsTwoPointer(string source, string pattern, int[] targetIndices) {
int maxRemovals = 0;
int j = 0, m = pattern.Length;
for (int x = 0, i = 0; i < targetIndices.Length && j != m; i++) {
int k = targetIndices[i];
while (x <= k && j < m) {
if (source[x++] == pattern[j]) j++;
}
if (j == m) break;
maxRemovals++;
}
return maxRemovals;
}
}Python employs a greedy, two-pointer technique to incrementally validate the removal of characters at indices defined by targetIndices. It continues until a necessary character in 'pattern' is improperly affected by a removal attempt.
Time Complexity: O(n * m), iterating through potential remotion targets for each character in source matched to pattern.
Space Complexity: O(1), involving minimal extra space.
Approach 3: Dynamic Programming
We define f[i][j] to represent the maximum number of deletions in the first i characters of source that match the first j characters of 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 ofsource, in which casef[i][j] = f[i-1][j] + int(i-1 \in targetIndices); - If
source[i-1] = pattern[j-1], we can match thei-th character ofsource, in which casef[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 source and pattern, respectively.
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];
}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]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search with Subsequence Validation | Time Complexity: O(n * log(m)); n being the length of 'source' and m the length of targetIndices. |
| Two Pointer Greedy Approach | Time Complexity: O(n * m), iterating through potential remotion targets for each character in source matched to pattern. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search with Subsequence Validation | O(n log k) | O(n) | Best general solution when removable indices are large and you need an efficient check. |
| Two Pointer Greedy Simulation | O(n + k) to O(nk) depending on validation frequency | O(n) | Useful for understanding the subsequence validation process or when constraints are small. |
Frequently asked questions
Is Find Maximum Removals From Source String easy or hard?
The problem is rated Medium because it requires recognizing a monotonic property and combining binary search with subsequence validation. The individual techniques are standard, but identifying that binary search on the answer works is the key insight.
Find Maximum Removals From Source String Python/Java solution
Most implementations follow the same structure: binary search the number of removable indices and validate with a two-pointer subsequence check. The logic is identical across Python, Java, C++, C#, and JavaScript with only syntax differences.
How to solve Find Maximum Removals From Source String in O(n log k)?
Use binary search on the number of characters removed. For each candidate value, mark the first k indices as removed and run a two-pointer subsequence check to see if the pattern still appears in the source string. If it does, increase k; otherwise decrease it. This efficiently finds the maximum valid removal count.
What is the best approach for Find Maximum Removals From Source String?
Binary search with subsequence validation is the most efficient and commonly expected solution. The idea is to binary search the number of removable characters and check whether the pattern remains a subsequence after removing those indices. Each validation uses a two-pointer subsequence scan of the string.
Is Find Maximum Removals From Source String asked at Google/Amazon/Meta?
Problems involving subsequence validation, binary search on answer, and greedy pointer scanning frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of binary search over monotonic conditions and string subsequence checks.
What data structure is used in Find Maximum Removals From Source String?
The solution mainly uses arrays or boolean markers to track removed indices, along with two-pointer traversal of the strings. Binary search is applied on the answer space while the subsequence check operates directly on the string characters.
What is the time complexity of Find Maximum Removals From Source String?
The optimal solution runs in O(n log k) time where n is the length of the source string and k is the number of removable indices. Each binary search step performs a linear subsequence check using two pointers. Space complexity is O(n) for tracking removed positions.