Maximum Number of Removable Characters — Problem & Solution
Maximum Number of Removable Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Number of Removable Characters is a medium coding problem on arrays, strings and binary search, asked in Amazon, Google and Salesforce interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Binary Search, Two Pointers
- 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 <= 1000000 <= removable.length < s.lengthremovable holds distinct indices into s.p is a subsequence of s.s and p consist of lowercase English letters.
Hints for Maximum Number of Removable Characters
Hint 1
If
kremovals still leavepa subsequence, so does any smallerk— the property is monotone.Hint 2
So binary search
kand check each candidate directly.Hint 3
The check is a linear subsequence scan that skips removed positions.
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
kover[0, removable.length]. stillSub(k): markremovable[0 … k-1]as gone, then two-pointer throughsmatchingp, skipping marked positions.- Keep the largest
kthat 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 ansJava
private static boolean stillSubsequence(String s, String p, int[] removable, int count) {
boolean[] gone = new boolean[s.length()];
for (int i = 0; i < count; i++) gone[removable[i]] = true;
int j = 0;
for (int i = 0; i < s.length() && j < p.length(); i++) {
if (!gone[i] && s.charAt(i) == p.charAt(j)) j++;
}
return j == p.length();
}
public static int maximumRemovals(String s, String p, int[] removable) {
int lo = 0, hi = removable.length, ans = 0;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (stillSubsequence(s, p, removable, mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}C++
static bool stillSubsequence(string& s, string& p, vector<int>& removable, int count) {
vector<bool> gone(s.size(), false);
for (int i = 0; i < count; i++) gone[removable[i]] = true;
int j = 0;
for (int i = 0; i < (int) s.size() && j < (int) p.size(); i++) {
if (!gone[i] && s[i] == p[j]) j++;
}
return j == (int) p.size();
}
int maximumRemovals(string s, string p, vector<int>& removable) {
int lo = 0, hi = (int) removable.size(), ans = 0;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (stillSubsequence(s, p, removable, 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.