Maximum Number of Removable Characters

Medium
831.

Maximum Number of Removable Characters

Maximum Number of Removable Characters is a medium coding problem on arrays, strings and binary search, asked in Amazon, Google and Salesforce interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} p
 * @param {number[]} removable
 * @return {number}
 */
var maximumRemovals = function(s, p, removable) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Maximum Number of Removable Characters

  1. Hint 1

    If k removals still leave p a subsequence, so does any smaller k — the property is monotone.

  2. Hint 2

    So binary search k and check each candidate directly.

  3. 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

  1. Binary search k over [0, removable.length].
  2. stillSub(k): mark removable[0 … k-1] as gone, then two-pointer through s matching p, skipping marked positions.
  3. 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

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings