Code Implementation

class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        def is_subsequence(removed_set):
            i = j = 0
            while i < len(s) and j < len(p):
                if i in removed_set or s[i] != p[j]:
                    i += 1
                else:
                    i += 1
                    j += 1
            return j == len(p)

        left, right = 0, len(removable)
        answer = 0
        while left <= right:
            mid = (left + right) // 2
            removed_set = set(removable[:mid])
            if is_subsequence(removed_set):
                answer = mid
                left = mid + 1
            else:
                right = mid - 1
        return answer
      

class Solution {
public:
    bool isSubsequence(const string& s, const string& p, const unordered_set<int>& removed) {
        int i = 0, j = 0;
        while (i < s.size() && j < p.size()) {
            if (removed.count(i) || s[i] != p[j]) {
                ++i;
            } else {
                ++i;
                ++j;
            }
        }
        return j == p.size();
    }
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int left = 0, right = removable.size(), answer = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            unordered_set<int> removed(removable.begin(), removable.begin() + mid);
            if (isSubsequence(s, p, removed)) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return answer;
    }
};
      

class Solution {
    private boolean isSubsequence(String s, String p, Set<Integer> removed) {
        int i = 0, j = 0;
        while (i < s.length() && j < p.length()) {
            if (removed.contains(i) || s.charAt(i) != p.charAt(j)) {
                i++;
            } else {
                i++;
                j++;
            }
        }
        return j == p.length();
    }
    public int maximumRemovals(String s, String p, int[] removable) {
        int left = 0, right = removable.length, answer = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            Set<Integer> removed = new HashSet<>();
            for (int i = 0; i < mid; i++) removed.add(removable[i]);
            if (isSubsequence(s, p, removed)) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return answer;
    }
}
      

/**
 * @param {string} s
 * @param {string} p
 * @param {number[]} removable
 * @return {number}
 */
var maximumRemovals = function(s, p, removable) {
    function isSubsequence(removedSet) {
        let i = 0, j = 0;
        while (i < s.length && j < p.length) {
            if (removedSet.has(i) || s[i] !== p[j]) {
                i++;
            } else {
                i++;
                j++;
            }
        }
        return j === p.length;
    }
    let left = 0, right = removable.length, answer = 0;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let removedSet = new Set(removable.slice(0, mid));
        if (isSubsequence(removedSet)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return answer;
};
      

Problem Description

Given three inputs:

• A string s
• A string p
• An integer array removable of indices in s

• Each index in removable is valid and unique.
• There is always at least one valid solution (possibly k=0).
• Characters removed are not reused.

Thought Process

At first glance, the problem seems to require checking, for each possible k, whether p is still a subsequence of s after removing the specified characters. A brute-force approach would be to try every possible value of k from 0 to removable.length, remove those characters, and check if p is a subsequence each time.
However, this can be very inefficient for large inputs. Instead, we should look for an optimized way to find the largest possible k efficiently. Since the more characters we remove, the less likely p is to remain a subsequence, we notice that the property is monotonic: if p is not a subsequence after removing k characters, it will not be a subsequence for any k' > k. This suggests using binary search to efficiently find the maximum k.
We also need to quickly check if p is a subsequence after removing a set of indices. For this, we can use a set to mark removed indices and perform a standard two-pointer subsequence check, skipping removed indices.

Solution Approach

We can break the solution into the following steps:

1. Binary Search on k:
   • We perform binary search on the range 0 to removable.length to find the largest k such that p is still a subsequence after removing the first k indices from removable.
2. Efficient Subsequence Check:
   • For a given k, we use a set to store the indices that have been "removed" (i.e., should be ignored).
   • We use two pointers: one for s and one for p. We iterate through s, skipping any character at a removed index. If the character matches the current character in p, we advance the pointer for p. If we reach the end of p, it is a subsequence.
3. Putting it Together:
   • For each mid-value in the binary search, build the set of removed indices and check if p is a subsequence.
   • If so, move the search window to try a larger k; otherwise, try a smaller k.

Example Walkthrough

Let's walk through an example:
Input:

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

• First, try k=0: No removals. p="ab" is a subsequence of s: YES.
• Try k=1: Remove index 3 (s[3]='a'). s becomes: "abc_cb" (underscore means removed, but indices are unchanged). Is "ab" a subsequence? YES (positions 0 and 1).
• Try k=2: Remove indices 3 and 1. s becomes: "a_c_cb". Is "ab" a subsequence? YES (positions 0 and 4).
• Try k=3: Remove indices 3, 1, 0. s becomes: "_c_cb". Is "ab" a subsequence? NO (there is no 'a' before 'b').

Time and Space Complexity

Brute-force approach:

• For each k from 0 to removable.length, remove the characters and check if p is a subsequence.
• Each subsequence check is O(|s|), and there are O(|removable|) possible k values.
• Total: O(|s| × |removable|)

• Binary search over k (O(log |removable|) iterations).
• Each iteration, check if p is a subsequence (O(|s|) time).
• Total: O(|s| × log |removable|)
• Space: O(|removable|) for the set of removed indices.

Summary

To solve the Maximum Number of Removable Characters problem, we take advantage of the monotonic relationship between the number of removals and the subsequence property. By applying binary search over the possible number of removals and efficiently checking for the subsequence condition using a set and two pointers, we find the largest valid k quickly. This approach is both elegant and efficient, reducing the time complexity from linear in the number of removals to logarithmic, while keeping the code readable and maintainable.