Maximum Number of Removable Characters — LeetCode 1898 Python Solution

The 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).

Example

Input

s = "abcacb", p = "ab", removable = [3,1,0]

Output

2

Explanation

After removing the characters at indices 3 and 1, "abcacb" becomes "accb".

Python solution

class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        def check(k: int) -> bool:
            rem = [False] * len(s)
            for i in removable[:k]:
                rem[i] = True
            i = j = 0
            while i < len(s) and j < len(p):
                if not rem[i] and p[j] == s[i]:
                    j += 1
                i += 1
            return j == len(p)

        l, r = 0, len(removable)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1898. Maximum Number of Removable Characters is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems