#1898

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Number of Removable Characters

Use binary search and a subsequence check to find the largest removable prefix that still keeps p inside s.

Problem Statement

You are given a string s, a string p, and an array removable of distinct indices in s. The goal is to remove characters using only the first k positions from removable and keep p as a subsequence of the remaining characters.

You need to return the largest k that still works. The interview trick is to stop thinking about every possible removal count separately and instead ask an easier yes or no question: after removing the first k indices, can p still be matched inside s with order preserved?

Examples

Example 1

Input: s = "abcacb", p = "ab", removable = [3,1,0]

Output: 2

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

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

If you remove the first index in the array removable, "abc" is no longer a subsequence.

Constraints

1 <= p.length <= s.length <= 105
0 <= removable.length < s.length
0 <= removable[i] < s.length
p is a subsequence of s.
s and p both consist of lowercase English letters.
The elements in removable are distinct.

Solution Approach

1. Reduce the problem to a yes or no check

This problem becomes much simpler once you define a helper function for a fixed k. Mark the first k indices from removable as deleted, then walk through s and p with two pointers. Skip deleted characters in s, advance the p pointer only when characters match, and return true if all of p is matched. That helper captures the exact failure mode of this problem: a removal plan breaks only when the subsequence order can no longer be completed.

2. Binary search the maximum removable prefix

The valid answer space is monotonic. If removing the first k indices still leaves p as a subsequence, then removing fewer than k indices must also work. If k fails, any larger value must fail too because it removes even more characters from the same ordered prefix of removable. That makes this a clean binary search on k from 0 to removable.length.

3. Implement the check efficiently

For each binary search step, build a boolean removed array of size s.length and mark removable[0..k-1]. Then scan s once while trying to match p. This keeps each check linear in s.length, avoids rebuilding strings, and makes the pattern easy to reason about. The common trade-off here is extra O(n) marking space in exchange for a simple and reliable subsequence test.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Let n be s.length and m be removable.length. Each binary search step performs one linear subsequence check over s and marks up to k removed positions, so each check is O(n + k), which is O(n) in the worst case. Because binary search runs O(log m) checks, the total time is O(n log m). The extra space is O(n) for the removed marker array.

What Interviewers Usually Probe

They expect you to notice monotonicity in the answer, not binary search on string positions.
They want a subsequence checker that skips removed indices without physically rebuilding s.
They are testing whether you can separate the search over k from the validation logic.

Common Pitfalls or Variants

Common pitfalls

Rebuilding the filtered string on every check adds unnecessary overhead and obscures the two-pointer logic.
Using binary search without proving why a larger removable prefix cannot recover once a smaller one already fails.
Forgetting that only the first k indices in removable count, not any arbitrary set of k deletions.

Follow-up variants

Return the minimum k that makes p stop being a subsequence instead of the maximum k that keeps it valid.
Allow multiple queries with different p values, which pushes you to rethink repeated subsequence checks.
Replace subsequence matching with substring matching, which breaks the simple two-pointer validation used here.

FAQ

Why is binary search valid for Maximum Number of Removable Characters?

Because the answer space is monotonic. If p is still a subsequence after removing the first k indices, then it will also be a subsequence for every smaller k. Once a value fails, every larger value fails as well.

How do you check whether p is still a subsequence after k removals?

Mark the first k indices from removable as deleted. Then scan s with one pointer and p with another. Skip deleted positions in s, match characters in order, and succeed only if the p pointer reaches the end.

Why not physically remove characters from s each time?

Building a new string for every binary search step adds overhead and is unnecessary. This problem only needs to know whether a position is usable during the subsequence scan, so a removed marker array is simpler and faster.

What is the main failure mode in this problem?

The subsequence check fails when deletions remove too many useful positions from s, so the two-pointer scan can no longer match all characters of p in order. That is the exact boundary binary search is trying to find.

What pattern should I remember from this problem title?

Remember binary search over the valid answer space combined with a linear feasibility check. In Maximum Number of Removable Characters, the feasibility check is a subsequence test after marking the first k removable indices.

terminal

Solution

Solution 1: Binary Search

We notice that if removing the characters at the first $k$ indices in $\textit{removable}$ still makes $p$ a subsequence of $s$, then removing the characters at $k \lt k' \leq \textit{removable.length}$ indices will also satisfy the condition. This monotonicity allows us to use binary search to find the maximum $k$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        def check(k: int) -> bool:
            rem = [False] * len(s)
            for i in removable[:k]:
                rem[i] = True
            i = j = 0
            while i < len(s) and j < len(p):
                if not rem[i] and p[j] == s[i]:
                    j += 1
                i += 1
            return j == len(p)

        l, r = 0, len(removable)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Continue Practicing

#1855 maximum distance between a pair of values #1961 check if string is a prefix of array #1813 sentence similarity iii