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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Removable Characters

Number: 2027

Difficulty: Medium

Paid? No

Companies: Amazon, Snowflake, Alphonso

Problem Description

Given two strings s and p (with p being a subsequence of s) and an array removable that lists unique indices in s, determine the maximum number k such that removing the characters at the first k indices in removable from s leaves p as a subsequence of the resulting string.

Key Insights

  • Use binary search to efficiently determine the maximum k possible.
  • For a given k, simulate the removal of characters from s using a set of indices from removable.
  • Check if p is still a subsequence in the modified s using a two-pointer approach.
  • The problem leverages checking for subsequences with removal simulation to verify a candidate k.

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(n) in the worst-case scenario to store removed indices.

Solution

We perform a binary search on the number of removable indices k. For each candidate k, we mark the indices from removable (from 0 to k-1) as removed. Then, by using two pointers, one iterates over s (skipping removed indices) and another iterates over p, checking if all characters of p appear in order. The binary search allows us to efficiently find the largest k such that p remains a subsequence. Key data structures include a set to store removed indices and simple pointer variables for iterating s and p.

Code Solutions

# Define the function to check if p is a subsequence of s after k removals
def is_subsequence(s, p, removed):
    # Pointer for p
    p_index = 0
    # Iterate over each character in s
    for i in range(len(s)):
        # Skip characters that are removed
        if i in removed:
            continue
        # If the current character matches the current character in p, move p pointer
        if s[i] == p[p_index]:
            p_index += 1
            # If complete subsequence matched, return True
            if p_index == len(p):
                return True
    return p_index == len(p)

def maximumRemovals(s, p, removable):
    low, high = 0, len(removable)
    # Binary search for the maximum k
    while low <= high:
        mid = (low + high) // 2
        # Mark the first mid indices as removed
        removed_set = set(removable[:mid])
        # Check if p is still a subsequence after these removals
        if is_subsequence(s, p, removed_set):
            low = mid + 1  # Try to remove more characters
        else:
            high = mid - 1  # Too many removals, reduce k
    return high

# Example usage:
print(maximumRemovals("abcacb", "ab", [3,1,0]))  # Expected output: 2
← Back to All Questions