Maximum Number of Removable Characters
Problem
Given s, p (p is a subsequence of s), and an array removable of distinct indices into s. Return the largest k such that removing removable[0..k-1] from s still leaves p as a subsequence.
s = "abcacb", p = "ab", removable = [3,1,0]2def maximum_removals(s, p, removable):
def ok(k):
removed = set(removable[:k])
j = 0
for i, c in enumerate(s):
if i in removed: continue
if c == p[j]:
j += 1
if j == len(p): return True
return False
lo, hi = 0, len(removable)
while lo < hi:
mid = (lo + hi + 1) // 2
if ok(mid): lo = mid
else: hi = mid - 1
return lofunction maximumRemovals(s, p, removable) {
function ok(k) {
const removed = new Set(removable.slice(0, k));
let j = 0;
for (let i = 0; i < s.length; i++) {
if (removed.has(i)) continue;
if (s[i] === p[j]) { if (++j === p.length) return true; }
}
return false;
}
let lo = 0, hi = removable.length;
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2);
if (ok(mid)) lo = mid; else hi = mid - 1;
}
return lo;
}class Solution {
public int maximumRemovals(String s, String p, int[] removable) {
int lo = 0, hi = removable.length;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (ok(s, p, removable, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}
boolean ok(String s, String p, int[] removable, int k) {
Set<Integer> rem = new HashSet<>();
for (int i = 0; i < k; i++) rem.add(removable[i]);
int j = 0;
for (int i = 0; i < s.length(); i++) {
if (rem.contains(i)) continue;
if (s.charAt(i) == p.charAt(j)) { if (++j == p.length()) return true; }
}
return false;
}
}bool ok(string& s, string& p, vector<int>& r, int k) {
unordered_set<int> rem(r.begin(), r.begin() + k);
int j = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (rem.count(i)) continue;
if (s[i] == p[j]) { if (++j == (int)p.size()) return true; }
}
return false;
}
int maximumRemovals(string s, string p, vector<int>& removable) {
int lo = 0, hi = removable.size();
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (ok(s, p, removable, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}Explanation
We want the largest prefix length k of removable such that after deleting those indices, p is still a subsequence of s. The key insight: if removing the first k indices keeps p a subsequence, then removing fewer also does. That monotonicity lets us binary-search k.
The check ok(k) marks the first k entries of removable as deleted (using a set for fast lookup), then does a simple subsequence scan: walk through s, skip deleted positions, and advance a pointer j through p whenever characters match. If j reaches the end of p, it is still a subsequence.
The binary search uses mid = (lo + hi + 1) // 2 to bias upward. If ok(mid) is true we keep that many removals and try more (lo = mid); otherwise we back off (hi = mid - 1).
Example: s = "abcacb", p = "ab", removable = [3,1,0]. Removing the first 2 indices (3 and 1) still leaves an 'a' and a later 'b', so p survives, but removing all 3 (also index 0) does not. The answer is 2.
Each check is linear in the string length, and binary search runs only a logarithmic number of checks, so it is efficient.