# Maximum Number of Removable Characters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-removable-characters)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-removable-characters
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, String
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [Moveworks](https://scaleengineer.com/companies/moveworks)
---
## Problem
You are given two strings `s` and `p` where `p` is a **subsequence** of `s`. You are also given a **distinct 0-indexed** integer array `removable` containing a subset of indices of `s` (`s` is also **0-indexed**).

You want to choose an integer `k` (`0 <= k <= removable.length`) such that, after removing `k` characters from `s` using the **first** `k` indices in `removable`, `p` is still a **subsequence** of `s`. More formally, you will mark the character at `s[removable[i]]` for each `0 <= i < k`, then remove all marked characters and check if `p` is still a subsequence.

Return _the **maximum**_ `k` _you can choose such that_ `p` _is still a **subsequence** of_ `s` _after the removals_.

A **subsequence** of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

**Example 1:**

**Input:** s = "abcacb", p = "ab", removable = [3,1,0]
**Output:** 2
**Explanation**: After removing the characters at indices 3 and 1, "a~~**b**~~c~~**a**~~cb" becomes "accb".
"ab" is a subsequence of "**a**cc**b**".
If we remove the characters at indices 3, 1, and 0, "~~**ab**~~c~~**a**~~cb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.

**Example 2:**

**Input:** s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
**Output:** 1
**Explanation**: After removing the character at index 3, "abc~~**b**~~ddddd" becomes "abcddddd".
"abcd" is a subsequence of "**abcd**dddd".

**Example 3:**

**Input:** s = "abcab", p = "abc", removable = [0,1,2,3,4]
**Output:** 0
**Explanation**: If you remove the first index in the array removable, "abc" is no longer a subsequence.

**Constraints:**

* `1 <= p.length <= s.length <= 105`
* `0 <= removable.length < s.length`
* `0 <= removable[i] < s.length`
* `p` is a **subsequence** of `s`.
* `s` and `p` both consist of lowercase English letters.
* The elements in `removable` are **distinct**.

# Approaches
## Linear Scan
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`.
**Time:** O(R * S), where `R` is `removable.length` and `S` is `s.length`. Let the answer be `K_ans`. The loop runs `K_ans + 1` times. Inside the loop, creating the `removed` array takes `O(k)` and checking the subsequence takes `O(S)`. The total time is `O(K_ans * (K_ans + S))`. In the worst case, `K_ans` is `R`, leading to `O(R * (R+S))`, which simplifies to `O(R*S)` as `R < S`. This is too slow for the given constraints. · **Space:** O(S) to store the `removed` boolean array, where S is the length of string `s`.
**Pros:** Conceptually simple and easy to implement.
**Cons:** Highly inefficient due to repeated computations.; Will result in Time Limit Exceeded (TLE) on larger test cases.
### Explanation
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`.

```java
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();
    }
}
```
### Algorithm
*   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`.

## Binary Search on the Number of Removals
A more efficient approach leverages the monotonic nature of the problem. If removing `k` characters is possible (i.e., `p` is still a subsequence), then removing any number of characters fewer than `k` is also possible. Similarly, if removing `k` characters is not possible, then removing any number of characters more than `k` is also not possible. This monotonic property allows us to use binary search on the answer `k`. The search space for `k` will be from `0` to `removable.length`.
**Time:** O(S * log R), where `R` is `removable.length` and `S` is `s.length`. The binary search performs `O(log R)` iterations. Each iteration calls `isPossible(k)`, which takes `O(k + S)` time. The maximum value of `k` is `R`, so the check is `O(R + S)`. The total complexity is `O((R + S) * log R)`. Since `R < S`, this is often simplified to `O(S * log R)`. This is efficient enough for the given constraints. · **Space:** O(S) for the `removed` boolean array created inside the `isPossible` function in each iteration of the binary search.
**Pros:** Significantly more efficient than the linear scan.; Guaranteed to pass within the time limits.
**Cons:** Slightly more complex to conceptualize than the brute-force approach.
### Explanation
We perform a binary search on the possible values of `k`, which range from `0` to `removable.length`. For each `mid` value of `k` in our search, we have a helper function `isPossible(k)` that checks if `p` remains a subsequence after removing the first `k` characters from the `removable` array.

The `isPossible(k)` function works similarly to the check in the linear scan approach: it marks the first `k` indices from `removable` and then uses a two-pointer scan to verify the subsequence property.

In the binary search loop:
*   If `isPossible(mid)` is `true`, it means we can remove `mid` characters. This is a potential answer, so we save it. To find the *maximum* `k`, we need to see if we can remove even more characters, so we continue our search in the upper half (`low = mid + 1`).
*   If `isPossible(mid)` is `false`, it means `mid` is too large. We must reduce the number of removals, so we continue our search in the lower half (`high = mid - 1`).

The binary search continues until `low > high`, and the last successfully recorded `k` is the maximum possible value.

```java
class Solution {
    public int maximumRemovals(String s, String p, int[] removable) {
        int low = 0;
        int high = removable.length;
        int ans = 0;

        while (low <= high) {
            int k = low + (high - low) / 2;
            if (isPossible(s, p, removable, k)) {
                ans = k; // This k is possible, try for more
                low = k + 1;
            } else {
                high = k - 1; // This k is not possible, try for less
            }
        }
        return ans;
    }

    private boolean isPossible(String s, String p, int[] removable, int k) {
        boolean[] removed = new boolean[s.length()];
        for (int i = 0; i < k; i++) {
            removed[removable[i]] = true;
        }

        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();
    }
}
```
### Algorithm
*   Initialize `low = 0`, `high = removable.length`, and `ans = 0`.
*   While `low <= high`:
    *   Calculate `mid = low + (high - low) / 2`.
    *   Call a helper function `isPossible(mid)` to check if `p` is a subsequence after removing `mid` characters.
    *   If `isPossible(mid)` is true, it's a valid `k`. Store it (`ans = mid`) and search for a larger `k` (`low = mid + 1`).
    *   Otherwise, `mid` is too large. Search for a smaller `k` (`high = mid - 1`).
*   Return `ans`.

# Solutions
### Java

```java
boolean check ( int x ) { } int search ( int left , int right ) { while ( left < right ) { int mid = ( left + right + 1 ) >> 1 ; if ( check ( mid )) { left = mid ; } else { right = mid - 1 ; } } return left ; }
```

### JavaScript

```javascript
/** * @param {string} s * @param {string} p * @param {number[]} removable * @return {number} */ function maximumRemovals(
  s,
  p,
  removable,
) {
  const str_len = s.length;
  const sub_len = p.length;
  /** * @param {number} k * @return {boolean} */ function isSub(k) {
    const removed = new Set(removable.slice(0, k));
    let sub_i = 0;
    for (let str_i = 0; str_i < str_len; ++str_i) {
      if (s.charAt(str_i) === p.charAt(sub_i) && !removed.has(str_i)) {
        ++sub_i;
        if (sub_i >= sub_len) {
          break;
        }
      }
    }
    return sub_i === sub_len;
  }
  let left = 0;
  let right = removable.length;
  while (left < right) {
    const middle = (left + right) >> 1;
    if (isSub(middle + 1)) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }
  return left;
}

```

### CPP

```cpp
class Solution {
public:
  int maximumRemovals(string s, string p, vector<int> &removable) {
    int left = 0, right = removable.size();
    while (left < right) {
      int mid = left + right + 1 >> 1;
      if (check(s, p, removable, mid)) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
  bool check(string s, string p, vector<int> &removable, int mid) {
    int m = s.size(), n = p.size(), i = 0, j = 0;
    unordered_set<int> ids;
    for (int k = 0; k < mid; ++k) {
      ids.insert(removable[k]);
    }
    while (i < m && j < n) {
      if (ids.count(i) == 0 && s[i] == p[j]) {
        ++j;
      }
      ++i;
    }
    return j == n;
  }
};

```

### Python

```python
class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int: def check(k): i = j = 0 ids = set(removable[: k]) while i < m and j < n: if i not in ids and s[i] == p[j]: j += 1 i += 1 return j == n m, n = len(s), len(p) left, right = 0, len(removable) while left < right: mid = (left + right + 1) >> 1 if check(mid): left = mid else: right = mid - 1 return left

```