We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Removable Characters

Difficulty: Medium

Problem 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. 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. Return the maximum k you can choose such that p is still a subsequence of s after the removals.

Key Insights

  • The problem requires checking if p remains a subsequence of s after removing characters at specified indices.
  • A binary search can be utilized to efficiently determine the maximum k by checking subsequence validity for various values of k.
  • The two-pointer technique is effective in verifying if p is a subsequence of the modified s.

Space and Time Complexity

Time Complexity: O(n log m), where n is the length of s and m is the length of removable. Space Complexity: O(1), since we are using a constant amount of additional space.

Solution

The solution employs a binary search to find the maximum k value. For each candidate k, we simulate the removals and check if p can still be formed as a subsequence of s using a two-pointer technique.

  1. Use binary search on the range of k from 0 to the length of removable.
  2. For each midpoint k, mark the characters in s that would be removed.
  3. Use two pointers to check if p is still a subsequence of the modified s.
  4. Adjust the search range based on whether p remains a subsequence.

Code Solutions

def maximumRemovals(s: str, p: str, removable: List[int]) -> int:
    def canForm(k: int) -> bool:
        removed = set(removable[:k])  # Indices to be removed
        j = 0  # Pointer for p
        for i in range(len(s)):
            if i in removed:
                continue
            if j < len(p) and s[i] == p[j]:
                j += 1
        return j == len(p)

    left, right = 0, len(removable)
    while left < right:
        mid = (left + right + 1) // 2
        if canForm(mid):
            left = mid  # p can still be formed, try for a larger k
        else:
            right = mid - 1  # p cannot be formed, try a smaller k
    return left
← Back to All Questions