# Find Maximum Removals From Source String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-maximum-removals-from-source-string)
Canonical: https://scaleengineer.com/dsa/problems/find-maximum-removals-from-source-string
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table, String
---
## Problem
You are given a string `source` of size `n`, a string `pattern` that is a subsequence of `source`, and a **sorted** integer array `targetIndices` that contains **distinct** numbers in the range `[0, n - 1]`.

We define an **operation** as removing a character at an index `idx` from `source` such that:

* `idx` is an element of `targetIndices`.
* `pattern` remains a subsequence of `source` after removing the character.

Performing an operation **does not** change the indices of the other characters in `source`. For example, if you remove `'c'` from `"acb"`, the character at index 2 would still be `'b'`.

Return the **maximum** number of _operations_ that can be performed.

**Example 1:**

**Input:** source = "abbaa", pattern = "aba", targetIndices \= \[0,1,2\]

**Output:** 1

**Explanation:**

We can't remove `source[0]` but we can do either of these two operations:

* Remove `source[1]`, so that `source` becomes `"a_baa"`.
* Remove `source[2]`, so that `source` becomes `"ab_aa"`.

**Example 2:**

**Input:** source = "bcda", pattern = "d", targetIndices \= \[0,3\]

**Output:** 2

**Explanation:**

We can remove `source[0]` and `source[3]` in two operations.

**Example 3:**

**Input:** source = "dda", pattern = "dda", targetIndices \= \[0,1,2\]

**Output:** 0

**Explanation:**

We can't remove any character from `source`.

**Example 4:**

**Input:** source = "yeyeykyded", pattern = "yeyyd", targetIndices \= \[0,2,3,4\]

**Output:** 2

**Explanation:**

We can remove `source[2]` and `source[3]` in two operations.

**Constraints:**

* `1 <= n == source.length <= 3 * 103`
* `1 <= pattern.length <= n`
* `1 <= targetIndices.length <= n`
* `targetIndices` is sorted in ascending order.
* The input is generated such that `targetIndices` contains distinct elements in the range `[0, n - 1]`.
* `source` and `pattern` consist only of lowercase English letters.
* The input is generated such that `pattern` appears as a subsequence in `source`.

# Approaches
## Linear Search on Removals
This is a straightforward approach that directly checks each possible number of removals, `k`, in increasing order. We start by checking if we can remove `k=1` character, then `k=2`, and so on, up to `m` (the total number of removable indices).

For each `k`, we need to decide which `k` characters to remove. The key insight, which also forms the basis for the more efficient binary search approach, is that removing characters at earlier indices in the `source` string is the most disruptive to finding a subsequence. Since `targetIndices` is sorted, we can test the 'worst-case' scenario for `k` removals by attempting to remove the characters at the first `k` indices listed in `targetIndices`.

If `pattern` remains a subsequence after removing these `k` characters, we proceed to check `k+1`. The first time this check fails for a value `k`, we can conclude that the maximum number of removals is `k-1`.
**Time:** O(m * n), where `m` is the length of `targetIndices` and `n` is the length of `source`. The outer loop runs `m+1` times, and the subsequence check inside takes `O(n)` time. · **Space:** O(n) to store the boolean array for removed indices, where `n` is the length of `source`. This could be considered O(m) if we use a Set, where `m` is the length of `targetIndices`.
**Pros:** Simple to understand and implement.; Correctly solves the problem by testing every possibility for the number of removals.
**Cons:** This approach is inefficient for large inputs and may result in a 'Time Limit Exceeded' error on platforms with strict time limits.
### Explanation
The algorithm iterates through the number of removals `k` from 1 to `targetIndices.length`. In each iteration, it simulates the removal of the first `k` indices from `targetIndices`. A helper function, `isSubsequence`, is used to determine if `pattern` is still a subsequence of the modified `source`.

This helper function can be implemented using a two-pointer method. One pointer, `i`, traverses the `source` string, and another pointer, `j`, traverses the `pattern` string. The `source` pointer `i` skips any character whose index is marked for removal. When `source.charAt(i)` matches `pattern.charAt(j)`, we advance the `pattern` pointer `j`. If `j` reaches the end of the `pattern`, it means we have found a valid subsequence.

The main loop continues until the `isSubsequence` check fails. If it fails for `k` removals, the answer is `k-1`. If the loop finishes completely, it means all `m` characters can be removed.

```java
class Solution {
    public int maximumRemovals(String source, String pattern, int[] targetIndices) {
        int maxRemovals = 0;
        for (int k = 0; k <= targetIndices.length; k++) {
            if (isPossible(source, pattern, targetIndices, k)) {
                maxRemovals = k;
            } else {
                break;
            }
        }
        return maxRemovals;
    }

    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 p1 = 0; // pointer for source
        int p2 = 0; // pointer for pattern

        while (p1 < s.length() && p2 < p.length()) {
            if (removed[p1]) {
                p1++;
                continue;
            }
            if (s.charAt(p1) == p.charAt(p2)) {
                p2++;
            }
            p1++;
        }

        return p2 == p.length();
    }
}
```
### Algorithm
1. Let `m` be the length of `targetIndices`.
2. Iterate `k` from 1 to `m`.
3. For each `k`, create a set of removed indices containing the first `k` elements of `targetIndices`.
4. Check if `pattern` is a subsequence of `source` with these `k` characters removed using a helper function.
5. The helper function `isSubsequence` uses a two-pointer technique. One pointer for `source` and one for `pattern`. It iterates through `source`, skipping removed characters, and tries to match characters of `pattern` in order.
6. If `isSubsequence` returns `false` for the current `k`, it means we cannot remove `k` characters. The maximum number of removals is therefore `k-1`. Return `k-1`.
7. If the loop completes without returning, it means we can remove all `m` characters from `targetIndices`. Return `m`.

## Binary Search on Removals
A more efficient approach utilizes binary search on the answer. The number of removals we can perform has a monotonic property: if we can remove `k` characters, we can also remove any number of characters less than `k`. This allows us to binary search for the maximum `k` that is possible.

The search space for `k` is from 0 to `m` (the length of `targetIndices`). For any given `k` during the binary search, we need to determine if it's possible to remove `k` characters. As established in the previous approach, the most restrictive set of `k` characters to remove corresponds to the first `k` indices in the sorted `targetIndices` array. Therefore, our check function, `isPossible(k)`, will test if `pattern` remains a subsequence after removing the characters at `targetIndices[0]` through `targetIndices[k-1]`.
**Time:** O(n * log m), where `m` is `targetIndices.length` and `n` is `source.length`. The binary search performs `O(log m)` iterations, and each iteration involves a subsequence check that takes `O(n)` time. · **Space:** O(n) to store the boolean array for removed indices within the check function. This is called `log m` times, but the space is reused.
**Pros:** Highly efficient, significantly faster than a linear scan for large inputs.; Guaranteed to find the optimal solution due to the monotonic nature of the problem.
**Cons:** The logic for the `check` function (why checking the prefix of `targetIndices` is sufficient) is more subtle than in the linear scan approach.
### Explanation
We apply binary search on the number of removals, `k`, which can range from `0` to `targetIndices.length`. For each `k` we test, we check if it's a feasible number of removals.

The `isPossible(k)` check function works by creating a set of the first `k` indices from `targetIndices`. Then, it verifies if `pattern` is a subsequence of `source` when characters at these indices are ignored. This verification is done in `O(n)` time using a two-pointer method.

If `isPossible(k)` returns true, it means we can successfully remove `k` items. This value of `k` becomes our current best answer, and we search for a potentially larger `k` in the upper half of the search range (`low = k + 1`). If `isPossible(k)` is false, `k` is too large, so we must search for a smaller `k` in the lower half (`high = k - 1`).

This process continues until the search space is exhausted (`low > high`), at which point we have found the maximum `k` that works.

```java
class Solution {
    public int maximumRemovals(String source, String pattern, int[] targetIndices) {
        int low = 0;
        int high = targetIndices.length;
        int ans = 0;

        while (low <= high) {
            int k = low + (high - low) / 2;
            if (isPossible(source, pattern, targetIndices, k)) {
                ans = k; // k is a possible number of removals
                low = k + 1; // Try for more
            } else {
                high = k - 1; // k is too many, 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 p1 = 0; // pointer for source
        int p2 = 0; // pointer for pattern

        while (p1 < s.length() && p2 < p.length()) {
            if (removed[p1]) {
                p1++;
                continue;
            }
            if (s.charAt(p1) == p.charAt(p2)) {
                p2++;
            }
            p1++;
        }

        return p2 == p.length();
    }
}
```
### Algorithm
1. Initialize search boundaries `low = 0`, `high = targetIndices.length`.
2. Initialize a variable `ans = 0` to store the maximum possible removals.
3. While `low <= high`:
    a. Calculate the middle point `k = low + (high - low) / 2`.
    b. Use a helper function `isPossible(k)` to check if removing `k` characters is possible. This function simulates removing the first `k` indices from `targetIndices` and checks if `pattern` is still a subsequence of `source`.
    c. If `isPossible(k)` is true:
        i. This means we can remove at least `k` characters. We store this as a potential answer: `ans = k`.
        ii. We try for a larger number of removals by moving the lower bound: `low = k + 1`.
    d. If `isPossible(k)` is false:
        i. This means `k` is too many removals. We need to try a smaller number.
        ii. We reduce the search space by moving the upper bound: `high = k - 1`.
4. After the loop terminates, `ans` will hold the maximum value of `k` for which `isPossible(k)` was true. Return `ans`.

# Solutions
### Java

```java
class Solution {
public
  int maxRemovals(String source, String pattern, int[] targetIndices) {
    int m = source.length(), n = pattern.length();
    int[][] f = new int[m + 1][n + 1];
    final int inf = Integer.MAX_VALUE / 2;
    for (var g : f) {
      Arrays.fill(g, -inf);
    }
    f[0][0] = 0;
    int[] s = new int[m];
    for (int i : targetIndices) {
      s[i] = 1;
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        f[i][j] = f[i - 1][j] + s[i - 1];
        if (j > 0 && source.charAt(i - 1) == pattern.charAt(j - 1)) {
          f[i][j] = Math.max(f[i][j], f[i - 1][j - 1]);
        }
      }
    }
    return f[m][n];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxRemovals(string source, string pattern, vector<int> &targetIndices) {
    int m = source.length(), n = pattern.length();
    vector<vector<int>> f(m + 1, vector<int>(n + 1, INT_MIN / 2));
    f[0][0] = 0;
    vector<int> s(m);
    for (int i : targetIndices) {
      s[i] = 1;
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        f[i][j] = f[i - 1][j] + s[i - 1];
        if (j > 0 && source[i - 1] == pattern[j - 1]) {
          f[i][j] = max(f[i][j], f[i - 1][j - 1]);
        }
      }
    }
    return f[m][n];
  }
};

```

### Python

```python
class Solution:
    def maxRemovals(self, source: str, pattern: str, targetIndices: List[int]) -> int: m, n = len(source), len(pattern) f = [[- inf] * (n + 1) for _ in range(m + 1)] f[0][0] = 0 s = set(targetIndices) for i, c in enumerate(source, 1): for j in range(n + 1): f[i][j] = f[i - 1][j] + int((i - 1) in s) if j and c == pattern[j - 1]: f[i][j] = max(f[i][j], f[i - 1][j - 1]) return f[m][n]

```