Maximum Number of Removable Characters

Medium

Asked by:

46 views

Topics:

ArraysStringsTwo PointersBinary Search

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

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. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.

Return the maximum k you can choose such that p is still a subsequence of s after the removals.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example 1:

Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb".
"ab" is a subsequence of "accb".
If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.

Example 2:

Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1
Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd".
"abcd" is a subsequence of "abcddddd".

Example 3:

Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0
Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.

Constraints:

1 <= p.length <= s.length <= 10⁵
0 <= removable.length < s.length
0 <= removable[i] < s.length
p is a subsequence of s.
s and p both consist of lowercase English letters.
The elements in removable are distinct.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum lengths of `s` and `p`, and the maximum length of the `removable` array?
Can `s` or `p` be empty strings? What happens if `removable` is empty?
Does the `removable` array contain valid indices within the string `s` (i.e., are all indices in bounds)?
If there are multiple possible maximum numbers of removable characters, is any valid maximum acceptable, or is there some other criteria to choose one?
If `p` is not a subsequence of `s` even without removing any characters, what should the function return?

Brute Force Solution

Approach

The brute force strategy involves checking every possible combination to find the largest number of characters we can remove from a string while still ensuring another string remains a subsequence. It's like trying all possibilities, one at a time, to see which one works best. We systematically remove different sets of characters and then check if the target string is still hidden within the modified string.

Here's how the algorithm would work step-by-step:

Start by considering that we remove no characters at all from the original string.
Then, try removing just one character from the original string, testing every possible character that could be removed.
Next, try removing two characters from the original string, testing every possible pair of characters that could be removed.
Continue increasing the number of removed characters, each time testing all the possible combinations of characters that could be removed.
For each set of removed characters, check if the target string is still a subsequence of the modified string (the original string with those characters removed). A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Keep track of the largest number of removed characters for which the target string is still a subsequence.
After testing all possible combinations of removed characters, return the largest number that allowed the target string to remain a subsequence.

Code Implementation

def maximum_removable_characters_brute_force(string_one, string_two, removable_indices):
    maximum_removals = 0
    number_of_removable_indices = len(removable_indices)

    for i in range(2 ** number_of_removable_indices):
        indices_to_remove = []
        for j in range(number_of_removable_indices):
            if (i >> j) & 1:
                indices_to_remove.append(removable_indices[j])

        indices_to_remove.sort()
        modified_string = list(string_one)

        # Mark characters for removal by replacing them with an empty string
        for index in indices_to_remove:
            modified_string[index] = ''

        modified_string = "".join(modified_string)

        # Check if string_two is a subsequence of the modified string
        string_two_index = 0
        modified_string_index = 0

        # If string_two is empty, any removals are a valid solution
        if not string_two:
            maximum_removals = max(maximum_removals, len(indices_to_remove))
            continue

        while string_two_index < len(string_two) and modified_string_index < len(modified_string):
            if string_two[string_two_index] == modified_string[modified_string_index]:
                string_two_index += 1
            modified_string_index += 1

        # Update maximum removals if string_two is still a subsequence
        if string_two_index == len(string_two):
            # If subsequence, track maximum removals
            maximum_removals = max(maximum_removals, len(indices_to_remove))

    return maximum_removals

Big(O) Analysis

Time Complexity

O(2^n * m) – The brute force approach considers all possible subsets of removable characters from string 's' of length 'n'. Generating all subsets takes O(2^n) time. For each subset, we construct the modified string and then check if string 't' of length 'm' is a subsequence of the modified string. Subsequence checking takes O(m) time in the worst case. Thus, the overall time complexity is O(2^n * m).

Space Complexity

O(1) – The brute force solution, as described, does not utilize any significant auxiliary data structures. It iteratively removes characters and checks for subsequences, likely using boolean flags or index variables to track the subsequence status, the count of removed characters, and potentially loop counters. These variables consume constant space, irrespective of the input string lengths. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

We want to find the most characters we can remove while still keeping a specific word as a subsequence of another. Instead of trying to remove every possible combination of characters, we'll use a smarter way of checking if a word is still a subsequence after removing some characters. This efficient approach avoids lots of unnecessary work.

Here's how the algorithm would work step-by-step:

Imagine we're trying to guess the largest number of characters we can remove. We'll start by guessing a number and checking if it's possible.
To check if our guess is valid, we'll remove the characters specified by the removable indices. This will give us a modified longer word.
Then, we'll go through both the modified longer word and the shorter word, checking if the shorter word is still a subsequence of the longer word.
If the shorter word is still a subsequence, that means we can remove at least that many characters. If not, our guess was too high.
We can use a method similar to the 'guess a number' game - if our guess was too low, we try a higher number; if it was too high, we try a lower number. We keep adjusting our guess until we find the maximum number of removable characters that still lets the shorter word be a subsequence of the longer word.

Code Implementation

def maximum_removable_characters(longer_word, shorter_word, removable_indices):
    left = 0
    right = len(removable_indices)
    maximum_removable = 0

    while left <= right:
        middle = (left + right) // 2
        
        # Check if we can remove this many characters
        if is_subsequence_after_removal(longer_word, shorter_word, removable_indices[:middle]):
            # If it's a subsequence, try removing more
            maximum_removable = middle
            left = middle + 1
        else:
            # If it's not, try removing fewer
            right = middle - 1

    return maximum_removable

def is_subsequence_after_removal(longer_word, shorter_word, indices_to_remove):
    modified_longer_word = ""
    indices_to_remove_set = set(indices_to_remove)

    for index, char in enumerate(longer_word):
        if index not in indices_to_remove_set:
            modified_longer_word += char

    short_pointer = 0
    long_pointer = 0

    # Check if shorter word is a subsequence
    while short_pointer < len(shorter_word) and long_pointer < len(modified_longer_word):
        if shorter_word[short_pointer] == modified_longer_word[long_pointer]:
            short_pointer += 1
        long_pointer += 1

    # Return True if shorter word is a subsequence
    # of the modified longer word
    return short_pointer == len(shorter_word)

Big(O) Analysis

Time Complexity

O(m*log(k) + n) – The algorithm uses binary search to find the maximum number of removable characters. The binary search iterates log(k) times, where k is the length of the removable indices array (which is at most the length of the longer string). Inside the binary search, the isSubsequence function is called. The isSubsequence function iterates through both the modified longer string (of length m, at most the original string length) and the shorter string of length n in linear time, O(m+n) for subsequence checking or simplified O(m) since m >= n. Therefore, the binary search dominates with m*log(k) within the loop plus O(n) for creating the modified longer string outside the loop. Thus, the overall time complexity is O(m*log(k) + n).

Space Complexity

O(N) – The provided solution utilizes binary search to find the maximum number of removable characters. The `removable` indices are used to create a modified version of the longer word in each iteration of the binary search. Creating this modified string potentially requires creating a new string of length at most N, where N is the length of the original longer word, to hold the remaining characters. Thus, the auxiliary space used scales linearly with the length of the longer word. This results in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty string s	Return 0 if s is null or empty, as no characters can be removed.
Null or empty string p	Return 0 if p is null or empty, as it vacuously satisfies being a subsequence.
Null or empty removable indices array	Return 0 if removable indices is null or empty, as no characters can be removed.
removable indices contains out-of-bounds indices	Filter out indices in removable that are out of bounds before processing.
removable indices contains duplicate indices	Handle duplicates by using a set to store unique removable indices; this avoids double removals.
p is not a subsequence of s even with no removals	Return 0 immediately since no removals will ever make p a subsequence.
s and p are identical strings	Return the length of the removable indices since all characters can be removed to make s an empty string (which trivially contains p).
Maximum length strings and removable indices to test for scalability	Ensure binary search and subsequence checking do not time out with maximum input size.

Null or empty string s

How to Handle:

Return 0 if s is null or empty, as no characters can be removed.

Null or empty string p

How to Handle:

Return 0 if p is null or empty, as it vacuously satisfies being a subsequence.

Null or empty removable indices array

How to Handle:

Return 0 if removable indices is null or empty, as no characters can be removed.

removable indices contains out-of-bounds indices

How to Handle:

Filter out indices in removable that are out of bounds before processing.

removable indices contains duplicate indices

How to Handle:

Handle duplicates by using a set to store unique removable indices; this avoids double removals.

p is not a subsequence of s even with no removals

How to Handle:

Return 0 immediately since no removals will ever make p a subsequence.

s and p are identical strings

How to Handle:

Return the length of the removable indices since all characters can be removed to make s an empty string (which trivially contains p).

Maximum length strings and removable indices to test for scalability

How to Handle:

Ensure binary search and subsequence checking do not time out with maximum input size.