Find Maximum Removals From Source String

Find Maximum Removals From Source String

What is this problem about?

In the Find Maximum Removals From Source String coding problem, you are given two strings, source and pattern, and an array of indices in source that are "removable." You want to remove the maximum number of characters from the removable indices such that pattern remains a subsequence of the modified source.

Why is this asked in interviews?

Google asks this to test your understanding of Dynamic Programming on Subsequences. It requires balancing the need to preserve a subsequence while maximizing removals. It evaluation your ability to define a state that tracks the progress in both the source and the pattern strings while identifying which removals are "safe."

Algorithmic pattern used

This is a 2D Dynamic Programming problem.

1. Let dp[i][j] be the maximum removals from the first $i$ characters of source such that the first $j$ characters of pattern are matched as a subsequence.
2. Transition:
   • At source[i-1]:
     • Always: You can choose to process the character. If it's a removable index, you can increment the removal count. dp[i][j] = dp[i-1][j] + (1 if removable).
     • If source[i-1] == pattern[j-1]: You can choose to use this character to match the pattern. In this case, you cannot remove it. dp[i][j] = max(dp[i][j], dp[i-1][j-1]).
3. The answer is dp[sourceLen][patternLen].

Example explanation

source = "abcde", pattern = "ae", removable = [1, 2, 3] (indices of 'b', 'c', 'd')

1. We need 'a' and 'e'.
2. 'a' is at index 0 (not removable). Stays.
3. 'b', 'c', 'd' are removable.
4. 'e' is at index 4 (not removable). Stays.
5. Since "ae" is formed by indices 0 and 4, we can remove all 3 characters at indices 1, 2, 3. Max removals: 3.

Common mistakes candidates make

• Greedy Approach: Trying to remove characters one by one and checking isSubsequence. This is $O(R imes N)$ and too slow.
• Wrong state: Storing "min removals" instead of "max removals" or failing to track the pattern index.
• Index mapping: Confusion between 0-based array indices and the 1-based DP table indices.

Interview preparation tip

For problems where you want to "Max/Min X while preserving subsequence Y," the state is usually dp[index_in_source][index_in_pattern]. This is a direct extension of the "Longest Common Subsequence" template.