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 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.
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.
This solution checks if 'pattern' remains a subsequence after a certain number of removals using a binary search strategy. A helper function is used to mark removable indices and checks if 'pattern' can still be formed from remaining characters.
Time Complexity: O(n * log(m)) where n is the length of the source and m is the length of targetIndices.
Space Complexity: O(n), for maintaining the 'removed' boolean array.
This technique uses a two-pointer approach to iteratively check and remove as long as 'pattern' remains a subsequence.
This approach attempts to remove as many characters as possible while pattern still forms a subsequence. It checks for every removal if it interrupts the formation of the pattern, and stops if it does, otherwise increases the count of valid removals.
Time Complexity: O(n*m), iterating through the source and pattern for every potential removal.
Space Complexity: O(1), uses constant space.
| Approach | Complexity |
|---|---|
| Binary Search with Subsequence Validation | Time Complexity: O(n * log(m)) where n is the length of the source and m is the length of targetIndices. |
| Two Pointer Greedy Approach | Time Complexity: O(n*m), iterating through the source and pattern for every potential removal. |
| 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. |
Leetcode Biweekly Contest 141 | 3316. Find Maximum Removals From Source String | DP | Codefod • CodeFod • 1,570 views views
Watch 7 more video solutions →Practice Find Maximum Removals From Source String with our built-in code editor and test cases.
Practice on FleetCode