Formatted question description: https://leetcode.ca/all/1898.html

# 1898. Maximum Number of Removable Characters

## Level

Medium

## Description

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

**cb” becomes “accb”.**~~a~~

“ab” is a subsequence of “**a**cc**b**”.

If we remove the characters at indices 3, 1, and 0, “** ab**c

**cb” becomes “ccb”, and “ab” is no longer a subsequence.**~~a~~

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 <= 10^5`

`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**.

## Solution

Use binary search. Initially, `low = 0`

and `high = removable.length`

. Each time, let `mid`

be the mean of `low`

and `high`

and check whether `p`

is still a subsequence of `s`

after removing `mid`

characters from `s`

according to `removable`

. The maximum possible `k`

can be found in this way.

```
class Solution {
public int maximumRemovals(String s, String p, int[] removable) {
int low = 0, high = removable.length;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (isPossible(s, p, removable, mid))
low = mid;
else
high = mid - 1;
}
return low;
}
public boolean isPossible(String s, String p, int[] removable, int k) {
int[] removes = new int[k];
for (int i = 0; i < k; i++)
removes[i] = removable[i];
Arrays.sort(removes);
StringBuffer sb = new StringBuffer(s);
for (int i = k - 1; i >= 0; i--)
sb.deleteCharAt(removes[i]);
return isSubsequence(p, sb.toString());
}
public boolean isSubsequence(String s, String t) {
if (s.length() == 0)
return true;
if (s.length() > t.length())
return false;
int sLength = s.length(), tLength = t.length();
int sIndex = 0, tIndex = 0;
while (sIndex < sLength && tIndex < tLength) {
char sChar = s.charAt(sIndex), tChar = t.charAt(tIndex);
if (sChar == tChar)
sIndex++;
tIndex++;
}
return sIndex == sLength;
}
}
```