Maximum Number of Removable Characters — Medium Problem & Solution

removable holds distinct indices into s. For a chosen k, you remove the characters at removable[0 … k-1] — the remaining characters keep their order.

Difficulty: Medium
Topics: Arrays, Strings, Two Pointers, Binary Search
Asked at: Amazon, Google, Salesforce
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

removable holds distinct indices into s. For a chosen k, you remove the characters at removable[0 … k-1] — the remaining characters keep their order.

Return the largest k for which p is still a subsequence of what remains.

Example 1

Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation: Removing indices 3 and 1 leaves "acb", which still contains "ab".

Example 2

Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1

Example 3

Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0

Constraints

1 <= p.length <= s.length <= 100000
0 <= removable.length < s.length
removable holds distinct indices into s.
p is a subsequence of s.
s and p consist of lowercase English letters.

How to solve Maximum Number of Removable Characters

The removals are nested: the first k indices are a prefix of the first k + 1. So more removals can only hurt, which makes the property monotone and binary-searchable, with a linear subsequence test per candidate.

Approach

Binary search k over [0, removable.length].
stillSub(k): mark removable[0 … k-1] as gone, then two-pointer through s matching p, skipping marked positions.
Keep the largest k that passes.

Why it works

Removing a superset of characters can only destroy subsequence matches, never create one, so feasibility is downward closed and the boundary is unique. The greedy subsequence match is correct because matching each character of p at its earliest possible position never blocks a later match.

Complexity

Time — O(n log r) where r is the number of removable indices
Space — O(n)

Pitfalls

Trying removals one at a time is O(n · r) and times out.
The marks must be rebuilt per candidate, not accumulated across the search.
The answer can be 0, so the search has to include it.

Reference solution

Python

from typing import List

def maximumRemovals(s: str, p: str, removable: List[int]) -> int:
    def still_sub(count: int) -> bool:
        gone = [False] * len(s)
        for i in range(count):
            gone[removable[i]] = True
        j = 0
        for i, ch in enumerate(s):
            if j == len(p):
                break
            if not gone[i] and ch == p[j]:
                j += 1
        return j == len(p)

    lo, hi, ans = 0, len(removable), 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if still_sub(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

JavaScript

var maximumRemovals = function(s, p, removable) {
    var stillSub = function(count) {
        var gone = [];
        for (var t = 0; t < s.length; t++) gone.push(false);
        for (var i = 0; i < count; i++) gone[removable[i]] = true;
        var j = 0;
        for (var x = 0; x < s.length && j < p.length; x++) {
            if (!gone[x] && s.charAt(x) === p.charAt(j)) j++;
        }
        return j === p.length;
    };
    var lo = 0, hi = removable.length, ans = 0;
    while (lo <= hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (stillSub(mid)) { ans = mid; lo = mid + 1; } else hi = mid - 1;
    }
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue