Find Maximum Removals From Source String - Practice Coding Problems

Find Maximum Removals From Source String - Problem

Array Hash Table Two Pointers String Dynamic Programming Medium

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.

Input & Output

Example 1 — Basic Removal

$ Input: source = "abcab", pattern = "ab", targetIndices = [1,4]

› Output: 2

💡 Note: We can remove characters at indices 1 and 4. After removal: source becomes "aca" → wait, this breaks the pattern. Let's recalculate: removing index 1 gives "acab", removing index 4 gives "abca". We can remove index 1 (b) to get "acab" which still contains "ab" as subsequence. We can also remove index 4 (b) to get "abca" which contains "ab". But removing both makes "aca" which doesn't contain "ab" as subsequence. So maximum is 1.

Example 2 — Multiple Options

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

› Output: 1

💡 Note: Pattern "aba" needs specific characters. We can remove at most 1 character while keeping "aba" as a subsequence.

Example 3 — No Removals Possible

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

› Output: 0

💡 Note: Since pattern equals source, we cannot remove any characters without breaking the pattern subsequence.

Constraints

1 ≤ n ≤ 3 × 10³
1 ≤ pattern.length ≤ n
1 ≤ targetIndices.length ≤ n
targetIndices is sorted in ascending order
The characters in source and pattern are lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Given source string, pattern, and removable indices

Removal Strategy

Determine which characters can be safely removed

Pattern Check

Ensure pattern remains as subsequence after removal

Key Takeaway

🎯 Key Insight: Use DP to optimally balance character removal with pattern preservation

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Meta 12

The key insight is to use dynamic programming to track the maximum removals possible while maintaining the pattern as a subsequence. The optimal approach uses memoized recursion to consider each character's role in pattern matching. Time: O(n×m), Space: O(n×m) where n is source length and m is pattern length.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Remove From Right to Left	O(k × n)	O(1)	Greedily remove characters from right to left while ensuring pattern remains a subsequence
Dynamic Programming - Optimal Matching	O(n × m)	O(n × m)	Use 2D DP to track optimal character removals while maintaining pattern subsequence
Brute Force - Try All Combinations	O(2^k × n)	O(k)	Generate all possible combinations of removals and check if pattern remains a subsequence

Greedy - Remove From Right to Left — Algorithm Steps

Sort target indices in descending order
For each index, try to remove the character
Check if pattern is still a subsequence
If yes, keep the removal; if no, skip it

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Descending

Process target indices from right to left

Try Remove

Attempt to remove each character and verify pattern

Keep Valid

Only keep removals that preserve pattern

Code -

solution.c — C

Time & Space Complexity

Time Complexity

⏱️

O(k × n)

k target indices, each requiring O(n) subsequence verification

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

30.8K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Remove From Right to Left — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler