NeetCode #289LC-1898MediumBinary Search
← Back to All Problems#289 · #1898 · Maximum Number of Removable Characters(可移除字符的最大数目)
📌 Problem Statement & Constraints
You are given strings
s and p, and an array removable of indices into s. You may remove the characters at the first k indices of removable. Return the largest k such that p is still a subsequence of the remaining string. Constraints: 1 <= p.length <= s.length <= 10^5, 0 <= removable.length < s.length; all indices are distinct.💡 Core Algorithmic Approaches
- Binary search on
k: "ispstill a subsequence after removing the firstkindices" is monotone ink. - For a given
k, mark the firstkindices as removed and run the standard two-pointer subsequence check. - Feasible when
pis fully matched. Use the upper-biased midpoint to find the largest feasiblek. - Rebuilding the removed set for each check costs O(k); using a boolean array of size
nkeeps each check O(n).
💻 Benchmark Python3 Implementation
class Solution:
def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
n = len(s)
def feasible(k: int) -> bool:
removed = [False] * n
for i in range(k):
removed[removable[i]] = True
j = 0 # pointer into p
for i, ch in enumerate(s):
if removed[i]:
continue # character removed
if j < len(p) and ch == p[j]:
j += 1
return j == len(p)
lo, hi = 0, len(removable)
while lo < hi:
mid = (lo + hi + 1) // 2 # upper-biased: maximise k
if feasible(mid):
lo = mid
else:
hi = mid - 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + m) log m) where m is the number of removable indices: each feasibility check is O(n + m).
💾 Space Complexity
O(n) for the removed array.
⚠️ Interview Pitfalls & Follow-ups
- Using the lower-biased midpoint with
lo = mid: infinite loop; the upper bias is required for maximisation. - Actually deleting characters from the string: O(n) per removal and error-prone; a boolean mask is cleaner.
- Forgetting that
pmust remain a subsequence, not a substring: the two-pointer check is the right one. - Assuming
k = 0is always feasible:pmight not be a subsequence ofseven without removals; the problem guarantees it is, but the binary search handles either case.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.