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

An operation is defined 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'.

Your task is to determine the maximum number of operations that can be performed.

Intuition

The goal is to maximize the number of characters we can remove from the source string while still maintaining pattern as a subsequence. One effective way to solve this problem is by using dynamic programming (DP).

The idea is to use a 2D DP table f[i][j], where f[i][j] represents the maximum number of deletions possible in the first i characters of source while matching the first j characters of pattern.

Here's the approach:

1. Initialization: Start with f[0][0] = 0, which means no deletions have been made initially, and all other entries can be set to -∞ because they are not achievable without operations.

2. Transition Logic:

   • Skipping a character: If you skip the i-th character of source, you can inherit the deletions from the previous character, i.e., f[i][j] = f[i-1][j]. Additionally, if i-1 is in targetIndices, increment the count by one deletion.
   • Matching a character: If the current character in source matches the corresponding character in pattern, you can choose this character to match, leading to f[i][j] = max(f[i][j], f[i-1][j-1]).

3. Result: The value f[m][n] (where m and n are lengths of source and pattern, respectively) will provide the maximum number of deletions that can be made without disturbing the subsequence relationship.

This approach effectively balances maintaining the subsequence and making the maximum allowable deletions.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

To solve this problem, we employ a dynamic programming approach. Here is a step-by-step explanation of the solution:

1. Define the DP Table:

   • We define a 2D list f where f[i][j] denotes the maximum number of deletions allowed in the first i characters of source while preserving the first j characters of the pattern.

2. Initialization:

   • Start with f[0][0] = 0 since initially there are no characters to remove and pattern is trivially a subsequence.
   • All other entries in f are initialized to -∞, representing that those states are not achievable without any operations.

3. Iterate over the source:

   • For each character c at index i-1 in source, iterate through each j from 0 to n (inclusive), where n is the length of pattern.

4. Two Main Choices in Transition:

   • Skip the character: If we decide to skip the i-th character of source, add potential deletions from previous state: f[i][j] = f[i-1][j] + int((i - 1) in s) where s is the set of targetIndices.
   • Match the character: If source[i-1] == pattern[j-1], we can use this character to match, therefore, f[i][j] = max(f[i][j], f[i-1][j-1]), indicating no change in the number of deletions.

5. Final Computation:

   • After processing all characters of source, the solution to the problem is found at f[m][n], where m is the length of source and n is the length of pattern.

By considering both possibilities at each step—whether to skip or match a character—and updating the DP table accordingly, we efficiently compute the maximum number of deletions that can be made while keeping pattern as a subsequence of source.

Example Walkthrough

Consider the following small example to illustrate the solution approach:

Suppose you have source = "abcde", pattern = "ace", and targetIndices = [0, 1, 3].

Step-by-Step Walkthrough:

1. Initialization:

   • Create a DP table f where f[i][j] tracks the maximum deletions in the first i characters of source while preserving the first j characters of pattern.
   • Start with f[0][0] = 0, meaning no deletions have been performed initially.
   • All other entries in the first row f[0][j] are initialized to -∞.

2. Iterate Over the source:

   i	source[i-1]	Explanation
   1	'a'	Matches pattern[0], update f[1][1] = f[0][0] = 0 (since we can use 'a')
   2	'b'	Can skip 'b', since it's in targetIndices, update f[2][0] = f[1][0] + 1 = 1 (one deletion because 'b' is removable)
   3	'c'	Matches pattern[1], update f[3][2] = f[2][1] = 0 (use 'c' for matching)
   4	'd'	Can skip 'd', since it's in targetIndices, update f[4][2] = f[3][2] + 1 = 1 (second deletion of 'd')
   5	'e'	Matches pattern[2], update f[5][3] = f[4][2] = 1 (use 'e' for matching)

3. Final Computation:

   After processing all characters, the value f[5][3] = 1 gives us the maximum number of operations (deletions) that can be performed while maintaining pattern as a subsequence of source.

In this example, we've removed two characters from source: 'b' at index 1 and 'd' at index 3, while ensuring that pattern "ace" remains a valid subsequence of source. The resulting string is "ace", and we achieved one deletion operation following the rule set.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(m * n) because it consists of two nested loops iterating over the length m of source and n of pattern. For each i from 1 to m, the inner loop iterates over j from 0 to n, performing constant-time operations inside.

The space complexity is also O(m * n) due to the creation of a 2D list f with dimensions (m + 1) x (n + 1). Each entry in this list stores an integer, representing the dynamic programming state.

Learn more about how to find time and space complexity quickly.