Find Maximum Removals From Source String

Medium

Asked by:

9 views

Topics:

StringsGreedy Algorithms

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.
pattern remains a subsequence of source after removing the character.

Performing an operation does not change the indices of the other characters in source. For example, if you remove 'c' from "acb", the character at index 2 would still be 'b'.

Return the maximum number of operations that can be performed.

Example 1:

Input: source = "abbaa", pattern = "aba", targetIndices = [0,1,2]

Output: 1

Explanation:

We can't remove source[0] but we can do either of these two operations:

Remove source[1], so that source becomes "a_baa".
Remove source[2], so that source becomes "ab_aa".

Example 2:

Input: source = "bcda", pattern = "d", targetIndices = [0,3]

Output: 2

Explanation:

We can remove source[0] and source[3] in two operations.

Example 3:

Input: source = "dda", pattern = "dda", targetIndices = [0,1,2]

Output: 0

Explanation:

We can't remove any character from source.

Example 4:

Input: source = "yeyeykyded", pattern = "yeyyd", targetIndices = [0,2,3,4]

Output: 2

Explanation:

We can remove source[2] and source[3] in two operations.

Constraints:

1 <= n == source.length <= 3 * 10³
1 <= pattern.length <= n
1 <= targetIndices.length <= n
targetIndices is sorted in ascending order.
The input is generated such that targetIndices contains distinct elements in the range [0, n - 1].
source and pattern consist only of lowercase English letters.
The input is generated such that pattern appears as a subsequence in source.

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:

Can you provide examples of the source string, target strings, and what constitutes a "removal" in those examples?
What are the constraints on the lengths of the source and target strings? Are they likely to be very long, or relatively short?
If a target string appears multiple times in the source string, can I remove all occurrences, or am I limited to a single removal per target string?
If no removals are possible, what should the function return? Should it return 0, -1, or throw an exception?
Are the target strings guaranteed to be unique, or might there be duplicate target strings in the input?

Brute Force Solution

Approach

The brute force approach to finding the maximum removals involves trying every possible combination of removals from the source string. We check if removing each combination of characters from the source string allows the target strings to be present as subsequences. We keep track of the maximum number of characters that can be removed while still allowing the target strings to be subsequences.

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

Consider all possible groups of characters we could remove from the original string.
For each of these groups of removals, create a new string where those characters are gone.
Check if all the target strings can still be found within this new, shorter string, appearing in the correct order, even if there are extra characters in between.
If all target strings can be found, count how many characters we removed to create this shorter string.
Keep track of the biggest number of removed characters we've found so far, as long as all the target strings are still present.
After trying all possible groups of removals, the biggest number we kept track of is the answer.

Code Implementation

def find_maximum_removals_from_source(source_string, target_strings):
    maximum_removals = 0
    number_of_characters_in_source = len(source_string)

    # Iterate through all possible subsets of removals.
    for i in range(2**number_of_characters_in_source):
        characters_to_remove = []
        for j in range(number_of_characters_in_source):
            if (i >> j) & 1:
                characters_to_remove.append(j)

        # Create a modified string with characters removed.
        modified_string = ""
        for k in range(number_of_characters_in_source):
            if k not in characters_to_remove:
                modified_string += source_string[k]

        # Check if all target strings are subsequences of the modified string.
        all_targets_are_subsequences = True
        for target_string in target_strings:
            target_index = 0
            modified_index = 0

            while target_index < len(target_string) and modified_index < len(modified_string):
                if target_string[target_index] == modified_string[modified_index]:
                    target_index += 1
                modified_index += 1

            # If the entire target string was not found as a subsequence, set flag to false.
            if target_index < len(target_string):
                all_targets_are_subsequences = False
                break

        # If all target strings are subsequences, update maximum removals.
        if all_targets_are_subsequences:

            # Update maximum removals if current removal count is greater
            number_of_removed_characters = len(characters_to_remove)
            maximum_removals = max(maximum_removals, number_of_removed_characters)

    return maximum_removals

Big(O) Analysis

Time Complexity

O(2^n * m * n) – The brute force approach considers all possible subsets of characters to remove from the source string of length n. This generates 2^n possible subsets. For each subset, we construct a modified string (in O(n) time). Then, we must check if all m target strings are subsequences of the modified string. Checking if a target string is a subsequence takes O(n) time in the worst case. Since we must check m target strings, subsequence checks take O(m*n) time. Thus the overall time complexity is O(2^n * (n + m * n)), which simplifies to O(2^n * m * n) because 2^n dominates n, and typically m is smaller than n^k for some fixed k.

Space Complexity

O(2^N) – The brute force approach considers all possible subsets of characters to remove from the source string. Each subset corresponds to a combination of characters removed, which can be represented as a binary string of length N (where N is the length of the source string), indicating whether each character is removed or not. Thus, the algorithm implicitly generates all 2^N possible subsets. While the plain English explanation does not explicitly mention a data structure to hold all subsets, the function call stack or temporary string construction in most implementations will occupy space proportional to the number of subsets to explore. Therefore, the space complexity is O(2^N).

Optimal Solution

Approach

The goal is to find the maximum number of words from a list that can be removed from a source string, such that the remaining string does not contain those words as substrings. The efficient way to tackle this problem is to use a strategy that prioritizes removing the words that cause the most conflicts.

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

First, try to figure out if each of the words that can be removed appear as parts of the remaining string. This can be efficiently done using a search algorithm.
Then, prioritize the words to remove, starting with the ones that appear most frequently within the source string.
For each word, test whether removing it would cause any of the other removable words to appear in the source string.
If removing a word prevents other removable words from appearing, keep track of this information.
Repeat the process, removing words and checking for new removable words until no more removable words can be removed without leaving those words as substrings of the remaining source string.
The maximum number of removals is the final answer.

Code Implementation

def find_maximum_removals(source_string, removable_words):
    removals_count = 0
    words_to_remove = list(removable_words)

    while True:
        words_appearing = {}
        for word in words_to_remove:
            if word in source_string:
                words_appearing[word] = source_string.count(word)

        if not words_appearing:
            break

        # Prioritize words appearing most frequently.
        word_to_remove = max(words_appearing, key=words_appearing.get)

        temp_source_string = source_string.replace(word_to_remove, "")
        is_safe_to_remove = True

        # Check if removing the word causes other words to appear.
        for other_word in words_to_remove:
            if other_word == word_to_remove:
                continue
            if other_word in temp_source_string:
                is_safe_to_remove = False
                break

        if is_safe_to_remove:
            source_string = temp_source_string
            words_to_remove.remove(word_to_remove)
            removals_count += 1
        else:
            words_to_remove.remove(word_to_remove)

    return removals_count

Big(O) Analysis

Time Complexity

O(m*n*k) – Let n be the length of the source string, m be the number of removable words, and k be the average length of the removable words. The algorithm iterates through the removable words (m times) attempting to remove them. For each word removal, it needs to check if other removable words are now substrings of the source string. This substring search can take O(n*k) time in the worst case (checking for each of the m words as substrings). Therefore the overall time complexity becomes O(m*n*k) because we check m words and the substring check takes O(n*k) time.

Space Complexity

O(N*M) – The space complexity is primarily determined by the need to store information about which words can be removed and how removing one word affects the appearance of others. This can be represented by an adjacency matrix or similar data structure where N is the number of words and M is the length of the source string. We may need to keep track of the start and end indices of each word within the source string to facilitate removal and checking for subsequent appearances, leading to O(N*M) to store all possible substring locations. Therefore the auxiliary space is O(N*M) where N is the number of words and M is the length of the source string.

Edge Cases

Case	How to Handle
Null source or target string	Throw IllegalArgumentException or return 0 if null strings are passed.
Empty source or target string	If target is empty return source length, if source is empty return 0.
Target string is longer than source string	Return 0 since the target string cannot be fully removed.
Source string contains characters not present in the target	These characters should be ignored, affecting the final removal count.
Target string has duplicate characters not present in source	The algorithm should consider these missing characters and stop when source characters are exhausted or no more copies are possible.
Very long source and target strings (performance)	Ensure that the chosen algorithm has an acceptable time complexity (e.g., optimized searching or counting). Consider memory allocation for large strings.
Source string is a permutation of the target string	In this case, return the length of the target string as the number of possible removals.
Source string has multiple occurrences of the target string	Algorithm must count correctly overlapping and non-overlapping removals

Null source or target string

How to Handle:

Throw IllegalArgumentException or return 0 if null strings are passed.

Empty source or target string

How to Handle:

If target is empty return source length, if source is empty return 0.

Target string is longer than source string

How to Handle:

Return 0 since the target string cannot be fully removed.

Source string contains characters not present in the target

How to Handle:

These characters should be ignored, affecting the final removal count.

Target string has duplicate characters not present in source

How to Handle:

The algorithm should consider these missing characters and stop when source characters are exhausted or no more copies are possible.

Very long source and target strings (performance)

How to Handle:

Ensure that the chosen algorithm has an acceptable time complexity (e.g., optimized searching or counting). Consider memory allocation for large strings.

Source string is a permutation of the target string

How to Handle:

In this case, return the length of the target string as the number of possible removals.

Source string has multiple occurrences of the target string

How to Handle:

Algorithm must count correctly overlapping and non-overlapping removals