Scale Engineer

Find Maximum Removals From Source String

Med
#2945Time: O(m * n), where `m` is the length of `targetIndices` and `n` is the length of `source`. The outer loop runs `m+1` times, and the subsequence check inside takes `O(n)` time.Space: O(n) to store the boolean array for removed indices, where `n` is the length of `source`. This could be considered O(m) if we use a Set, where `m` is the length of `targetIndices`.
Patterns
Two PointersDynamic Programming
Data structures
ArrayHash TableString

Prompt

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.

 

Example 1:

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

Output: 1

Explanation:

We can't remove source[0] but we can do either of these two operations:

  • Remove source[1], so that source becomes "a_baa".
  • Remove source[2], so that source becomes "ab_aa".

Example 2:

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

Output: 2

Explanation:

We can remove source[0] and source[3] in two operations.

Example 3:

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

Output: 0

Explanation:

We can't remove any character from source.

Example 4:

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

Output: 2

Explanation:

We can remove source[2] and source[3] in two operations.

 

Constraints:

  • 1 <= n == source.length <= 3 * 103
  • 1 <= pattern.length <= n
  • 1 <= targetIndices.length <= n
  • targetIndices is sorted in ascending order.
  • The input is generated such that targetIndices contains distinct elements in the range [0, n - 1].
  • source and pattern consist only of lowercase English letters.
  • The input is generated such that pattern appears as a subsequence in source.

Approaches

2 approaches with complexity analysis and trade-offs.

This is a straightforward approach that directly checks each possible number of removals, k, in increasing order. We start by checking if we can remove k=1 character, then k=2, and so on, up to m (the total number of removable indices).

For each k, we need to decide which k characters to remove. The key insight, which also forms the basis for the more efficient binary search approach, is that removing characters at earlier indices in the source string is the most disruptive to finding a subsequence. Since targetIndices is sorted, we can test the 'worst-case' scenario for k removals by attempting to remove the characters at the first k indices listed in targetIndices.

If pattern remains a subsequence after removing these k characters, we proceed to check k+1. The first time this check fails for a value k, we can conclude that the maximum number of removals is k-1.

Algorithm

  1. Let m be the length of targetIndices.
  2. Iterate k from 1 to m.
  3. For each k, create a set of removed indices containing the first k elements of targetIndices.
  4. Check if pattern is a subsequence of source with these k characters removed using a helper function.
  5. The helper function isSubsequence uses a two-pointer technique. One pointer for source and one for pattern. It iterates through source, skipping removed characters, and tries to match characters of pattern in order.
  6. If isSubsequence returns false for the current k, it means we cannot remove k characters. The maximum number of removals is therefore k-1. Return k-1.
  7. If the loop completes without returning, it means we can remove all m characters from targetIndices. Return m.

Walkthrough

The algorithm iterates through the number of removals k from 1 to targetIndices.length. In each iteration, it simulates the removal of the first k indices from targetIndices. A helper function, isSubsequence, is used to determine if pattern is still a subsequence of the modified source.

This helper function can be implemented using a two-pointer method. One pointer, i, traverses the source string, and another pointer, j, traverses the pattern string. The source pointer i skips any character whose index is marked for removal. When source.charAt(i) matches pattern.charAt(j), we advance the pattern pointer j. If j reaches the end of the pattern, it means we have found a valid subsequence.

The main loop continues until the isSubsequence check fails. If it fails for k removals, the answer is k-1. If the loop finishes completely, it means all m characters can be removed.

class Solution {    public int maximumRemovals(String source, String pattern, int[] targetIndices) {        int maxRemovals = 0;        for (int k = 0; k <= targetIndices.length; k++) {            if (isPossible(source, pattern, targetIndices, k)) {                maxRemovals = k;            } else {                break;            }        }        return maxRemovals;    }     private boolean isPossible(String s, String p, int[] removable, int k) {        boolean[] removed = new boolean[s.length()];        for (int i = 0; i < k; i++) {            removed[removable[i]] = true;        }         int p1 = 0; // pointer for source        int p2 = 0; // pointer for pattern         while (p1 < s.length() && p2 < p.length()) {            if (removed[p1]) {                p1++;                continue;            }            if (s.charAt(p1) == p.charAt(p2)) {                p2++;            }            p1++;        }         return p2 == p.length();    }}

Complexity

Time

O(m * n), where `m` is the length of `targetIndices` and `n` is the length of `source`. The outer loop runs `m+1` times, and the subsequence check inside takes `O(n)` time.

Space

O(n) to store the boolean array for removed indices, where `n` is the length of `source`. This could be considered O(m) if we use a Set, where `m` is the length of `targetIndices`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem by testing every possibility for the number of removals.

Cons

  • This approach is inefficient for large inputs and may result in a 'Time Limit Exceeded' error on platforms with strict time limits.

Solutions

class Solution {public  int maxRemovals(String source, String pattern, int[] targetIndices) {    int m = source.length(), n = pattern.length();    int[][] f = new int[m + 1][n + 1];    final int inf = Integer.MAX_VALUE / 2;    for (var g : f) {      Arrays.fill(g, -inf);    }    f[0][0] = 0;    int[] s = new int[m];    for (int i : targetIndices) {      s[i] = 1;    }    for (int i = 1; i <= m; ++i) {      for (int j = 0; j <= n; ++j) {        f[i][j] = f[i - 1][j] + s[i - 1];        if (j > 0 && source.charAt(i - 1) == pattern.charAt(j - 1)) {          f[i][j] = Math.max(f[i][j], f[i - 1][j - 1]);        }      }    }    return f[m][n];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem