Watch 10 video solutions for Maximum Number of Removable Characters, a medium level problem involving Array, Two Pointers, String. This walkthrough by NeetCode has 21,212 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).
You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.
Return the maximum k you can choose such that p is still a subsequence of s after the removals.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
Example 1:
Input: s = "abcacb", p = "ab", removable = [3,1,0] Output: 2 Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb". "ab" is a subsequence of "accb". If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence. Hence, the maximum k is 2.
Example 2:
Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6] Output: 1 Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd". "abcd" is a subsequence of "abcddddd".
Example 3:
Input: s = "abcab", p = "abc", removable = [0,1,2,3,4] Output: 0 Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.
Constraints:
1 <= p.length <= s.length <= 1050 <= removable.length < s.length0 <= removable[i] < s.lengthp is a subsequence of s.s and p both consist of lowercase English letters.removable are distinct.Problem Overview: You are given a string s, a subsequence target p, and an array removable representing indices in s that can be removed. The goal is to determine the maximum number k such that after removing the first k indices from removable, the string p is still a subsequence of s.
Approach 1: Iterative Validation (O(n * r) time, O(n) space)
Start by removing characters incrementally based on the order in removable. After each removal step, check whether p remains a subsequence of the modified string. The subsequence check uses a classic two pointers scan: one pointer walks through s, the other through p. If characters match, advance both pointers; otherwise only move the pointer on s. Continue until the subsequence condition fails. This approach is straightforward but inefficient because the subsequence validation runs after every removal step, producing worst-case O(n * r) time where n is the length of s and r is the length of removable. Use it when constraints are small or when building intuition for the problem.
Approach 2: Binary Search on Maximum k (O(n log r) time, O(n) space)
The key observation: if removing k characters still keeps p a subsequence, then removing fewer than k characters will also work. This monotonic behavior makes the problem perfect for binary search. Search the range [0, r] to find the largest valid k. For each midpoint k, mark the first k indices in removable as deleted using a boolean array. Then run a subsequence check using two pointers over the string. If p is still a subsequence, move the binary search window right; otherwise move left. Each validation scan costs O(n), and the binary search runs log r iterations, producing an overall complexity of O(n log r).
Recommended for interviews: Binary search with subsequence validation is the expected solution. It demonstrates recognition of monotonic properties and efficient search space reduction. Showing the iterative validation approach first proves you understand the problem mechanics, while the binary search optimization shows algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Validation | O(n * r) | O(n) | Useful for understanding the subsequence check logic or when input sizes are small. |
| Binary Search on Maximum k | O(n log r) | O(n) | Optimal approach for large inputs where repeatedly validating removals would be too slow. |