Problem Description

You have a string source of length n, a string pattern that is a subsequence of source, and a sorted array targetIndices containing distinct integers in the range [0, n-1].

An operation consists of removing a character at index idx from source where:

• idx must be an element in targetIndices
• After removing the character, pattern must still remain a subsequence of source

When you remove a character, the indices of other characters don't change. For example, if you remove the character at index 1 from "acb", the character 'b' remains at index 2.

The goal is to find the maximum number of operations (character removals) you can perform while ensuring pattern stays a subsequence of source.

Example walkthrough:

• If source = "abcab", pattern = "ab", and targetIndices = [0, 1, 2]
• You could potentially remove the character at index 2 ('c'), and pattern = "ab" would still be a subsequence of the resulting "abab"
• But you cannot remove characters at indices 0 or 1 without breaking the subsequence requirement

The solution uses dynamic programming where f[i][j] represents the maximum number of deletions possible when considering the first i characters of source and matching the first j characters of pattern. At each position, you decide whether to:

1. Skip the current character (and potentially delete it if its index is in targetIndices)
2. Match the current character with the pattern (if they're equal)

The answer is f[m][n] where m is the length of source and n is the length of pattern.

Intuition

The key insight is that we want to maximize deletions while maintaining pattern as a subsequence. This naturally leads to a dynamic programming approach where we track both our progress through source and pattern.

Think of it this way: as we scan through source, at each character we face a decision - should we use this character to match with pattern, or should we skip it (and potentially delete it)? The challenge is that we need to ensure we can still form the complete pattern subsequence after our deletions.

The critical observation is that we need to track two things simultaneously:

1. How many characters of source we've processed
2. How many characters of pattern we've successfully matched

This leads us to define our state as f[i][j] - the maximum deletions possible when we've looked at the first i characters of source and matched the first j characters of pattern.

At each position (i, j), we have two choices:

Choice 1: Skip the current character in source

• We move from f[i-1][j] to f[i][j] (processed one more character but didn't match any new pattern character)
• If this skipped character's index is in targetIndices, we can delete it, adding 1 to our deletion count

Choice 2: Match the current character (if possible)

• Only available when source[i-1] == pattern[j-1]
• We move from f[i-1][j-1] to f[i][j] (processed one more source character AND matched one more pattern character)
• We don't delete this character since we're using it for matching

The beauty of this approach is that by considering both options at each step and taking the maximum, we automatically find the optimal strategy that maximizes deletions while ensuring the pattern remains a subsequence. The final answer f[m][n] gives us the maximum deletions when we've processed all of source and matched all of pattern.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

We implement the dynamic programming solution using a 2D array f where f[i][j] represents the maximum number of deletions possible when considering the first i characters of source and matching the first j characters of pattern.

Initialization:

• Create a 2D array f of size (m+1) × (n+1) where m = len(source) and n = len(pattern)
• Initialize all values to -inf (negative infinity) to represent invalid states
• Set f[0][0] = 0 as the base case (no characters processed, no deletions made)
• Convert targetIndices to a set s for O(1) lookup time

State Transition: For each character at position i in source (1-indexed) and each possible matched position j in pattern (0 to n):

1. Skip current character in source:

   f[i][j] = f[i-1][j] + int((i-1) in s)

   • We inherit the state from f[i-1][j] (same pattern progress, one more source character processed)
   • If index i-1 (0-indexed) is in targetIndices, we can delete it, adding 1 to our count

2. Match current character (if possible):

   if j > 0 and source[i-1] == pattern[j-1]:
       f[i][j] = max(f[i][j], f[i-1][j-1])

   • Only applicable when j > 0 (we have pattern characters to match)
   • Only when characters match: source[i-1] == pattern[j-1]
   • We take the maximum of skipping vs matching to get the optimal choice

Why this works:

• By considering both options (skip/delete vs match) at each step, we explore all valid ways to form the pattern subsequence
• The -inf initialization ensures invalid states (where we can't form the required subsequence) are never chosen
• The maximum operation in the matching case ensures we pick the strategy that maximizes deletions

Final Answer: Return f[m][n], which represents the maximum deletions when we've processed all m characters of source and successfully matched all n characters of pattern.

Time Complexity: O(m × n) where m and n are the lengths of source and pattern Space Complexity: O(m × n) for the DP table

Example Walkthrough

Let's trace through a small example to understand how the dynamic programming solution works.

Input:

• source = "aba"
• pattern = "aa"
• targetIndices = [0, 2]

We need to find the maximum number of characters we can delete from indices 0 and 2 while keeping "aa" as a subsequence.

Setup:

• m = 3 (length of source), n = 2 (length of pattern)
• Create DP table f[4][3] initialized with -inf
• Set f[0][0] = 0 (base case)
• Convert targetIndices to set: s = {0, 2}

DP Table Evolution:

Initial state:

     j=0   j=1   j=2
i=0   0   -inf  -inf
i=1  -inf  -inf  -inf
i=2  -inf  -inf  -inf
i=3  -inf  -inf  -inf

Processing i=1 (source[0]='a'):

For j=0: Skip 'a'

• f[1][0] = f[0][0] + 1 = 0 + 1 = 1 (index 0 is in targetIndices, so +1)

For j=1: Can match 'a' with pattern[0]='a'

• Skip option: f[1][1] = f[0][1] + 1 = -inf + 1 = -inf
• Match option: f[1][1] = f[0][0] = 0
• Take max: f[1][1] = 0

Processing i=2 (source[1]='b'):

For j=0: Skip 'b'

• f[2][0] = f[1][0] + 0 = 1 + 0 = 1 (index 1 not in targetIndices)

For j=1: 'b' ≠ 'a', can only skip

• f[2][1] = f[1][1] + 0 = 0 + 0 = 0

For j=2: Cannot match (would need pattern[1]='a' but source[1]='b')

• Skip option: f[2][2] = f[1][2] + 0 = -inf

Processing i=3 (source[2]='a'):

For j=0: Skip 'a'

• f[3][0] = f[2][0] + 1 = 1 + 1 = 2 (index 2 is in targetIndices)

For j=1: Can match 'a' with pattern[0]='a'

• Skip option: f[3][1] = f[2][1] + 1 = 0 + 1 = 1
• Match option: f[3][1] = f[2][0] = 1
• Take max: f[3][1] = 1

For j=2: Can match 'a' with pattern[1]='a'

• Skip option: f[3][2] = f[2][2] + 1 = -inf
• Match option: f[3][2] = f[2][1] = 0
• Take max: f[3][2] = 0

Final DP Table:

     j=0   j=1   j=2
i=0   0   -inf  -inf
i=1   1    0   -inf
i=2   1    0   -inf
i=3   2    1    0

Answer: f[3][2] = 0

This means we can perform 0 deletions while maintaining "aa" as a subsequence. Why? Because we need both 'a' characters (at indices 0 and 2) to form the pattern "aa", so we cannot delete either of them even though they're in targetIndices.

Verification:

• Original: "aba" contains subsequence "aa" (using indices 0 and 2)
• If we delete index 0: "ba" doesn't contain "aa" ❌
• If we delete index 2: "ab" doesn't contain "aa" ❌
• Maximum deletions = 0 ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of the source string and n is the length of the pattern string. This is because the code uses two nested loops - the outer loop iterates through each character in source (m iterations), and the inner loop iterates through each possible position in pattern (n+1 iterations). Each operation inside the nested loops takes constant time O(1), including the set lookup operation (i - 1) in s and the comparison operations.

The space complexity is O(m × n). The dominant space usage comes from the 2D dynamic programming table f, which has dimensions (m + 1) × (n + 1). Additionally, the code creates a set s from targetIndices, which takes O(k) space where k is the length of targetIndices, but since k ≤ m, this doesn't affect the overall space complexity of O(m × n).

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

Common Pitfalls

1. Incorrect Initialization of Invalid States

Pitfall: Initializing the DP table with 0 instead of negative infinity, which can lead to accepting invalid subsequence formations.

Why it's problematic: If you initialize with 0, states that cannot form a valid subsequence would appear valid, potentially propagating incorrect values through the DP transitions.

Example of incorrect code:

# WRONG: Initializing with 0
dp = [[0] * (pattern_length + 1) for _ in range(source_length + 1)]

Solution: Always initialize with negative infinity except for the base case:

# CORRECT: Initialize with -inf, then set base case
dp = [[float('-inf')] * (pattern_length + 1) for _ in range(source_length + 1)]
dp[0][0] = 0

2. Index Confusion Between 0-based and 1-based

Pitfall: Mixing up the indexing when checking if an index is in targetIndices or when accessing characters from strings.

Why it's problematic: The DP table uses 1-based indexing for convenience (where dp[i][j] represents first i characters), but strings and targetIndices use 0-based indexing.

Example of incorrect code:

# WRONG: Using source_idx directly instead of source_idx - 1
if source_idx in removable_indices:  # This checks wrong index!
    dp[source_idx][pattern_idx] += 1

Solution: Always convert to 0-based when checking targetIndices or accessing string characters:

# CORRECT: Convert to 0-based index
if (source_idx - 1) in removable_indices:
    dp[source_idx][pattern_idx] += 1

# When accessing characters:
current_char = source[source_idx - 1]  # 0-based indexing

3. Forgetting to Handle the "Skip Without Deletion" Case

Pitfall: Only incrementing the removal count when skipping a character, without considering that some characters can be skipped but not deleted (if their index isn't in targetIndices).

Why it's problematic: The transition should always allow skipping a character; we just don't increment the deletion count if the index isn't removable.

Example of incorrect code:

# WRONG: Only updating when index is removable
if (source_idx - 1) in removable_indices:
    dp[source_idx][pattern_idx] = dp[source_idx - 1][pattern_idx] + 1
# Missing the else case!

Solution: Always inherit from the previous state, then conditionally add 1:

# CORRECT: Always update, conditionally increment
dp[source_idx][pattern_idx] = dp[source_idx - 1][pattern_idx]
if (source_idx - 1) in removable_indices:
    dp[source_idx][pattern_idx] += 1

4. Not Converting targetIndices to a Set

Pitfall: Using the list directly for membership checking, resulting in O(k) lookup time where k is the size of targetIndices.

Why it's problematic: This increases the overall time complexity from O(m×n) to O(m×n×k), which can cause timeouts for large inputs.

Example of incorrect code:

# WRONG: Using list for membership check
if (source_idx - 1) in targetIndices:  # O(k) operation
    dp[source_idx][pattern_idx] += 1

Solution: Convert to set once at the beginning:

# CORRECT: Convert to set for O(1) lookup
removable_indices = set(targetIndices)
if (source_idx - 1) in removable_indices:  # O(1) operation
    dp[source_idx][pattern_idx] += 1