class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        '''
        a valid k is one where
        after removing k caracters from s using the first k indexes in removable
        you get a string which is still a subseq of s
        https://leetcode.com/problems/maximum-number-of-removable-characters/
        '''

        def isSubseq(p,s):

            i=0
            j=0
            while i < len(p) and j < len(s):
                if p[i]!=s[j]:
                    j+=1
                else:
                    # if they match
                    i+=1
                    j+=1
            return i==len(p)

        def isValid(k,s,p):
            aset=set(removable[:k])
            sfiltered=''
            for i,c in enumerate(s):
                if i not in aset:
                    sfiltered+=c
            return isSubseq(p,sfiltered)

        start=0
        end=len(removable)
        # 3+0 //2 = 1

        while start < end:
            # print(start,end)
            if end-start==1:
                if isValid(end,s,p):
                    return end
                if isValid(start,s,p):
                    return start
                break
            mid=(start+end)//2

            if isValid(mid,s,p):
                start=mid
            else:
                end=mid-1


        return end