---
# System prepended metadata

title: 1898. Maximum Number of Removable Characters
tags: [Leetcode, Binary Search, Medium]

---

# 1898. Maximum Number of Removable Characters
###### tags: `Leetcode` `Medium` `Binary Search`
Link: https://leetcode.com/problems/maximum-number-of-removable-characters/description/
## 思路
binary search by value
每次binary search用双指针检查p是不是 被删完某些字母的arr 的substring
用map存下removable的每个值及它对应的index 这样每次check的时候我们可以在遍历arr的时候检查当下index是不是大于mid 如果大于mid就说明当下字母没有被删除
## Code
```java=
class Solution {
    public int maximumRemovals(String s, String p, int[] removable) {
        char[] arr = s.toCharArray();
        int start = 0, end = removable.length;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<removable.length; i++){
            map.put(removable[i], i);
        }
        while(start<end){
            int mid = start+(end-start)/2;
            if(check(arr, p, map, mid)) start = mid+1;
            else end = mid;
        }
        return start;
    }
    public boolean check(char[] arr, String p, Map<Integer, Integer> map, int mid) {
        int i1 = 0, i2 = 0;
        while (i1 < arr.length && i2 < p.length()) {
            char curr = arr[i1], curr2 = p.charAt(i2);
            if (map.getOrDefault(i1, Integer.MAX_VALUE)>mid && curr == curr2) i2++;
            i1++;
        }
        if (i2 == p.length()) return true;
        return false;
    }
}
```