Maximum Number of Removable Characters

This is a straightforward brute-force approach. We want to find the maximum k, so we can test each possible value of k starting from k=1 up to removable.length. For each k, we simulate the removal of the first k characters specified in the removable array. Then, we check if p is still a subsequence of the modified string s. The first time this check fails, we know that the maximum number of characters we could remove was k-1. If the check succeeds for all k, the answer is removable.length.

• Since k=0 is always a valid case (as p is initially a subsequence of s), we can start checking from k=1.
• Loop k from 1 to removable.length.
• Create a boolean array removed of size s.length().
• Mark the first k indices from removable as true in the removed array.
• Call a helper isSubsequence(s, p, removed).
• If isSubsequence returns false, then the maximum k is k-1. Return k-1.
• If the loop completes, return removable.length.

In this approach, we iterate through k from 1 to removable.length. In each iteration, we determine the set of indices to be removed, which are removable[0], ..., removable[k-1]. A boolean array of size s.length() is used to efficiently mark these indices.

A helper function, isSubsequence, is used to perform the check. This function iterates through s and p with two pointers. It advances the pointer for s in each step. If the character s[i] is not marked for removal and matches the current character in p, the pointer for p is also advanced.

If p is found to be a subsequence, the loop continues to the next k. If p is not a subsequence, it means k removals are too many. Since we are iterating k in increasing order, the maximum number of successful removals must be k-1. We can immediately return k-1.

If the loop finishes without returning, it implies that even with removable.length removals, p remains a subsequence. In this case, the answer is removable.length.

class Solution {
    public int maximumRemovals(String s, String p, int[] removable) {
        // k=0 is always possible. We check for k=1, k=2, ...
        for (int k = 1; k <= removable.length; k++) {
            boolean[] removed = new boolean[s.length()];
            // Mark first k indices as removed
            for (int i = 0; i < k; i++) {
                removed[removable[i]] = true;
            }
            
            if (!isSubsequence(s, p, removed)) {
                // If removing k characters fails, the max was k-1
                return k - 1;
            }
        }
        
        // If we can remove all characters in `removable` and p is still a subsequence
        return removable.length;
    }

    private boolean isSubsequence(String s, String p, boolean[] removed) {
        int i = 0; // pointer for s
        int j = 0; // pointer for p
        while (i < s.length() && j < p.length()) {
            if (!removed[i] && s.charAt(i) == p.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == p.length();
    }
}