⚡Flashcard Drill➔
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

  1. Binary search on k: "is p still a subsequence after removing the first k indices" is monotone in k.
  2. For a given k, mark the first k indices as removed and run the standard two-pointer subsequence check.
  3. Feasible when p is fully matched. Use the upper-biased midpoint to find the largest feasible k.
  4. Rebuilding the removed set for each check costs O(k); using a boolean array of size n keeps 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 p must remain a subsequence, not a substring: the two-pointer check is the right one.
  • Assuming k = 0 is always feasible: p might not be a subsequence of s even 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems