LeetCode Problem 3316

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Two Pointers, String, Dynamic Programming

Solution

LeetCode 3316 - Find Maximum Removals From Source String

Problem Understanding

We are given three inputs:

• source, the original string of length n
• pattern, a string that is guaranteed to already be a subsequence of source
• targetIndices, a sorted list of indices in source that are eligible for removal

An operation consists of removing a character whose index belongs to targetIndices. However, after every removal, pattern must still remain a subsequence of the resulting string.

A very important detail is that removals do not shift indices. Conceptually, a removed character simply becomes unavailable, while all other positions keep their original index values.

The goal is to determine the maximum number of removable positions from targetIndices such that, after all chosen removals have been applied, pattern is still a subsequence of source.

Another way to think about the problem is that every index in targetIndices is optional. We want to remove as many of them as possible while still being able to match every character of pattern in order inside the remaining characters of source.

The constraints are:

• n ≤ 3000
• pattern.length ≤ n
• targetIndices.length ≤ n

The relatively small limit of 3000 suggests that an O(n²) dynamic programming solution is completely feasible, while exponential or cubic approaches are not.

Several edge cases are important:

• pattern may be identical to source, making every character essential.
• Every index may belong to targetIndices.
• Characters in source may repeat many times, creating multiple possible subsequence matches.
• The optimal solution may require choosing a non-obvious subsequence alignment that maximizes removable positions.
• A greedy choice of matching the earliest or latest character is not necessarily optimal.

Approaches

Brute Force

A brute-force solution would consider every subset of targetIndices.

For each subset, we would remove those positions and check whether pattern is still a subsequence of the remaining characters in source.

The subsequence check can be performed in linear time, but there are 2^k possible subsets where k = len(targetIndices).

Since k can be as large as 3000, this approach is completely infeasible.

The reason it is correct is straightforward: it explicitly tries every possible set of removals and selects the largest valid one. However, the exponential search space makes it unusable.

Key Insight

Instead of deciding which indices to remove, we can think about which characters of source are used to form pattern.

Suppose a position belongs to targetIndices.

• If that position is used to match a character of pattern, it cannot be removed.
• If that position is not used, it can be removed.

Therefore, every matched position from targetIndices represents one removal opportunity that is lost.

Let:

• k = len(targetIndices)
• usedTargetIndices = number of matched positions that belong to targetIndices

Then:

maximum removals = k - usedTargetIndices

So the problem becomes:

Match pattern as a subsequence of source while minimizing how many matched positions come from targetIndices.

This is a classic dynamic programming problem.

Define:

dp[i][j] = minimum number of target indices used while matching the first j characters of pattern using the first i characters of source

At each source character, we can:

1. Skip it.
2. Use it to match the next pattern character if the characters are equal.

The transition cost is:

• 1 if the matched source position belongs to targetIndices
• 0 otherwise

The minimum cost alignment directly gives the answer.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^k · n)	O(1)	Enumerates every removable subset
Optimal DP	O(nm)	O(m)	Finds subsequence match with minimum removable-index usage

Here:

• n = len(source)
• m = len(pattern)

Algorithm Walkthrough

1. Create a boolean array removable of length n.

For every index in targetIndices, mark removable[idx] = True.

This allows constant-time checking of whether a source position belongs to the removable set. 2. Let m = len(pattern).

Create a DP array of length m + 1.

dp[j] represents the minimum number of removable positions consumed while matching the first j characters of pattern. 3. Initialize:

• dp[0] = 0
• All other states are set to infinity.

Matching an empty pattern requires no positions. 4. Process characters of source from left to right.

For each source position i:

• Copy the current DP state into newDp.
• The copy naturally represents the option of skipping this character.

5. If source[i] matches pattern[j], we may extend a previous subsequence match.

The transition is:

newDp[j + 1] =
    min(
        newDp[j + 1],
        dp[j] + cost
    )

where:

cost = 1 if i belongs to targetIndices
       0 otherwise

6. After processing all possible matches for this source character, replace dp with newDp.
7. After all characters have been processed, dp[m] contains the minimum number of removable positions that must remain in order to form pattern.
8. Let:

required = dp[m]

Then:

answer = len(targetIndices) - required

Why it works

Every valid subsequence alignment of pattern inside source corresponds to a set of source positions used for matching. Any matched position that belongs to targetIndices cannot be removed. Therefore, the number of removable operations equals the total number of removable indices minus the number of removable indices that must stay. The dynamic programming formulation examines all possible subsequence alignments and computes the minimum number of removable positions required. Since every transition preserves subsequence order and all possible matches are considered, the minimum cost found is optimal. Subtracting that minimum cost from the total number of removable indices yields the maximum number of operations.

Python Solution

from typing import List

class Solution:
    def maxRemovals(
        self,
        source: str,
        pattern: str,
        targetIndices: List[int]
    ) -> int:
        n = len(source)
        m = len(pattern)

        removable = [False] * n
        for idx in targetIndices:
            removable[idx] = True

        INF = 10**9

        dp = [INF] * (m + 1)
        dp[0] = 0

        for i in range(n):
            new_dp = dp[:]

            cost = 1 if removable[i] else 0

            for j in range(m - 1, -1, -1):
                if source[i] == pattern[j]:
                    new_dp[j + 1] = min(
                        new_dp[j + 1],
                        dp[j] + cost
                    )

            dp = new_dp

        required = dp[m]
        return len(targetIndices) - required

The implementation begins by constructing a boolean lookup array indicating which positions belong to targetIndices. This allows constant-time determination of whether using a source position incurs a cost.

The DP array stores the minimum number of removable positions required to match each prefix of pattern. Initially, only the empty pattern is reachable.

For each source character, a copy of the DP state is created. The copied state represents skipping the current source character. Whenever the current source character matches a pattern character, the algorithm attempts to extend an existing subsequence match.

The transition adds either zero or one depending on whether the current source position belongs to targetIndices.

After all source characters have been processed, the final state contains the minimum number of removable positions that must remain. Subtracting this value from the total number of removable positions produces the maximum number of operations.

Go Solution

func maxRemovals(source string, pattern string, targetIndices []int) int {
	n := len(source)
	m := len(pattern)

	removable := make([]bool, n)
	for _, idx := range targetIndices {
		removable[idx] = true
	}

	const INF = int(1e9)

	dp := make([]int, m+1)
	for i := 1; i <= m; i++ {
		dp[i] = INF
	}

	for i := 0; i < n; i++ {
		newDP := make([]int, m+1)
		copy(newDP, dp)

		cost := 0
		if removable[i] {
			cost = 1
		}

		for j := m - 1; j >= 0; j-- {
			if source[i] == pattern[j] {
				if dp[j]+cost < newDP[j+1] {
					newDP[j+1] = dp[j] + cost
				}
			}
		}

		dp = newDP
	}

	required := dp[m]
	return len(targetIndices) - required
}

The Go implementation follows exactly the same dynamic programming strategy as the Python version.

The main difference is explicit slice allocation and copying using make and copy. Since all computed values are bounded by the string length, integer overflow is not a concern. Empty and nil slices are handled naturally because the constraints guarantee at least one element in targetIndices.

Worked Examples

Example 1

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

Removable positions:

Index	Character	Removable
0	a	Yes
1	b	Yes
2	b	Yes
3	a	No
4	a	No

One optimal alignment is:

Pattern Character	Source Index
a	0
b	1
a	3

This uses two removable positions.

A better alignment is:

Pattern Character	Source Index
a	0
b	2
a	3

This still uses two removable positions.

No valid alignment uses fewer than two removable positions.

Therefore:

Quantity	Value
Total removable indices	3
Minimum required removable indices	2
Answer	1

Example 2

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

Possible match:

Pattern Character	Source Index
d	2

Index 2 is not removable.

Therefore:

Quantity	Value
Total removable indices	2
Required removable indices	0
Answer	2

Example 3

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

The entire string is required.

Pattern Character	Source Index
d	0
d	1
a	2

All removable positions must remain.

Quantity	Value
Total removable indices	3
Required removable indices	3
Answer	0

Example 4

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

An optimal subsequence alignment avoids as many removable positions as possible.

Quantity	Value
Total removable indices	4
Required removable indices	2
Answer	2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nm)	Each source position processes every pattern position once
Space	O(m)	Only one DP row is stored

Here:

• n = len(source)
• m = len(pattern)

The algorithm performs a dynamic programming transition for every (source position, pattern position) pair. Since only the current DP state is needed, the full O(nm) table can be compressed into a single O(m) array.

Test Cases

sol = Solution()

assert sol.maxRemovals("abbaa", "aba", [0, 1, 2]) == 1  # example 1
assert sol.maxRemovals("bcda", "d", [0, 3]) == 2  # example 2
assert sol.maxRemovals("dda", "dda", [0, 1, 2]) == 0  # example 3
assert sol.maxRemovals("yeyeykyded", "yeyyd", [0, 2, 3, 4]) == 2  # example 4

assert sol.maxRemovals("abc", "abc", [0, 1, 2]) == 0  # entire string required
assert sol.maxRemovals("abc", "a", [1, 2]) == 2  # match uses no removable index
assert sol.maxRemovals("aaaaa", "aa", [0, 1, 2, 3, 4]) == 3  # choose best alignment
assert sol.maxRemovals("abcde", "ace", [1, 3]) == 2  # removable indices unused
assert sol.maxRemovals("aaaa", "aaaa", [0, 1, 2, 3]) == 0  # every position needed
assert sol.maxRemovals("ababab", "ab", [0, 1, 2, 3, 4, 5]) == 4  # many alignments
assert sol.maxRemovals("z", "z", [0]) == 0  # minimum size input

Test Case Summary

Test	Why
"abbaa", "aba"	Official example
"bcda", "d"	Pattern matched using non-removable position
"dda", "dda"	No removals possible
"yeyeykyded", "yeyyd"	Official complex example
"abc", "abc"	Entire source required
"abc", "a"	All removable positions can be deleted
"aaaaa", "aa"	Multiple repeated-character alignments
"abcde", "ace"	Removable positions irrelevant
"aaaa", "aaaa"	Every character must remain
"ababab", "ab"	Many possible subsequence choices
"z", "z"	Smallest valid input

Edge Cases

Pattern Equals Source

When pattern and source are identical, every character is required for the subsequence match. A buggy implementation might incorrectly assume some matching positions can be replaced. The DP correctly discovers that all characters must be used, producing zero removable operations.

Repeated Characters With Many Alignments

Inputs such as "aaaaa" and "aa" contain many possible subsequence embeddings. A greedy strategy that always picks the earliest or latest match may keep unnecessary removable positions. The DP explores all valid alignments and chooses the one with the minimum removable-index cost.

All Removable Indices Can Be Deleted

Consider source = "abc", pattern = "a", and targetIndices = [1,2]. The pattern can be matched entirely using a non-removable position. The DP assigns zero cost to that match, resulting in the maximum answer of two removals.

Every Index Is Removable

When all source positions belong to targetIndices, the answer depends entirely on how many positions must be preserved to form pattern. The dynamic programming formulation naturally handles this case because every matched position contributes a cost of one, and the algorithm minimizes the number of such required positions.