Watch 8 video solutions for Find Maximum Removals From Source String, a medium level problem involving Array, Hash Table, Two Pointers. This walkthrough by CodeFod has 1,570 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |