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

Find Maximum Removals From Source String

Number: 3487

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a string source, a subsequence string pattern, and a sorted array targetIndices representing indices in source that can be removed, return the maximum number of removal operations that can be performed such that pattern remains a subsequence of source. During each removal the indices of remaining characters remain unchanged.

Key Insights

  • Use binary search to determine the maximum count of removable indices.
  • For each candidate number of removals, simulate removals by marking the characters at the specified indices.
  • Verify if pattern remains a subsequence of the modified source using a two-pointers approach.
  • Since removals do not shift the indices, a boolean array can easily represent which characters are removed.

Space and Time Complexity

Time Complexity: O(n * log m) where n is the length of source and m is the length of targetIndices (m ≤ n) Space Complexity: O(n) for the boolean array used for simulation

Solution

The solution uses a binary search over the possible number of operations (from 0 up to the length of targetIndices). For each candidate count mid, mark the first mid indices from targetIndices as removed in the source string. Then, using a two-pointers technique, check if pattern is a subsequence of the modified source string. If the pattern can be found, try a larger candidate; otherwise, reduce the candidate count. This binary search framework efficiently finds the maximum number of removals possible while ensuring the pattern remains a subsequence.

Code Solutions

# Python implementation

def maximumRemovals(source, pattern, targetIndices):
    # Function to check if pattern is a subsequence of source after removals
    def isSubsequence(removals):
        removed = [False] * len(source)
        # mark the first 'removals' indices as removed
        for i in range(removals):
            removed[targetIndices[i]] = True
        j = 0  # pointer for pattern
        # iterate over source characters
        for i in range(len(source)):
            if removed[i]:
                continue  # skip removed characters
            if source[i] == pattern[j]:
                j += 1
                if j == len(pattern):
                    return True
        return j == len(pattern)
    
    low, high, ans = 0, len(targetIndices), 0
    # binary search for maximum removals
    while low <= high:
        mid = (low + high) // 2
        if isSubsequence(mid):
            ans = mid  # candidate valid, try to remove more
            low = mid + 1
        else:
            high = mid - 1
    return ans

# Example usage:
# source = "abbaa", pattern = "aba", targetIndices = [0,1,2]
# print(maximumRemovals(source, pattern, targetIndices))
← Back to All Questions