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

Find Maximum Removals From Source String

Difficulty: Medium

Problem Description

You are given a string source of size n, a string pattern that is a subsequence of source, and a sorted integer array targetIndices that contains distinct numbers in the range [0, n - 1]. We define an operation as removing a character at an index idx from source such that idx is an element of targetIndices and pattern remains a subsequence of source after removing the character. Perform the operation as many times as possible and return the maximum number of operations that can be performed.

Key Insights

  • The characters in pattern must remain a subsequence after each removal.
  • Use a two-pointer approach to check if pattern is a subsequence of source efficiently.
  • Maintain a count of valid removals based on how they impact the subsequence relationship.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of source and m is the length of pattern. Space Complexity: O(1), as we use a constant amount of space outside of the input.

Solution

To solve the problem, we can employ a two-pointer technique to verify if pattern is a subsequence of source after hypothetical removals. Initially, we can check how many characters from targetIndices can be removed without breaking the subsequence condition. By iterating through targetIndices, we can simulate the removal of each character and check if pattern still remains a subsequence of the modified source.

Code Solutions

def can_form_subsequence(source, pattern, removed_index):
    # Function to check if pattern is a subsequence of source
    j = 0  # Pointer for pattern
    for i in range(len(source)):
        if i == removed_index:  # Skip the removed character
            continue
        if j < len(pattern) and source[i] == pattern[j]:
            j += 1
    return j == len(pattern)

def max_removals(source, pattern, targetIndices):
    max_operations = 0
    for idx in targetIndices:
        if can_form_subsequence(source, pattern, idx):
            max_operations += 1
    return max_operations
← Back to All Questions