Find Maximum Removals From Source String

Medium
1663.

Find Maximum Removals From Source String

Find Maximum Removals From Source String is a medium coding problem on arrays, strings and hash table, asked in Google interviews.

You are given a string source of length n, a string pattern that is a subsequence of source, and a sorted array targetIndices of distinct indices in [0, n - 1].

An operation removes the character at some index idx of source, provided that idx is in targetIndices and pattern is still a subsequence of source afterwards. Removing a character does not shift the indices of the other characters.

Return the maximum number of operations that can be performed.

Example 1

Input
source = "abbaa", pattern = "aba", targetIndices = [0,1,2]
Output
1
Explanation
Removing index 0, 1 or 2 alone keeps "aba" as a subsequence, but removing any two of them breaks it.

Example 2

Input
source = "bcda", pattern = "d", targetIndices = [0,3]
Output
2
Explanation
Both index 0 ('b') and index 3 ('a') can go; "d" is still there.

Example 3

Input
source = "dda", pattern = "dda", targetIndices = [0,1,2]
Output
0
Explanation
The pattern is the whole string, so nothing can be removed.

Constraints

  • 1 <= n == source.length <= 3 * 10^3
  • 1 <= pattern.length <= n
  • 1 <= targetIndices.length <= n
  • targetIndices is sorted in ascending order and its values are distinct
  • 0 <= targetIndices[i] <= n - 1
  • source and pattern consist only of lowercase English letters
  • pattern is a subsequence of source
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} source
 * @param {string} pattern
 * @param {number[]} targetIndices
 * @return {number}
 */
var maxRemovals = function(source, pattern, targetIndices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Maximum Removals From Source String — Solution

Find Maximum Removals From Source String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find Maximum Removals From Source String is a medium coding problem on arrays, strings and hash table, asked in Google interviews.

Problem statement

You are given a string source of length n, a string pattern that is a subsequence of source, and a sorted array targetIndices of distinct indices in [0, n - 1].

An operation removes the character at some index idx of source, provided that idx is in targetIndices and pattern is still a subsequence of source afterwards. Removing a character does not shift the indices of the other characters.

Return the maximum number of operations that can be performed.

Example 1

Input: source = "abbaa", pattern = "aba", targetIndices = [0,1,2]
Output: 1
Explanation: Removing index 0, 1 or 2 alone keeps "aba" as a subsequence, but removing any two of them breaks it.

Example 2

Input: source = "bcda", pattern = "d", targetIndices = [0,3]
Output: 2
Explanation: Both index 0 ('b') and index 3 ('a') can go; "d" is still there.

Example 3

Input: source = "dda", pattern = "dda", targetIndices = [0,1,2]
Output: 0
Explanation: The pattern is the whole string, so nothing can be removed.

Constraints

  • 1 <= n == source.length <= 3 * 10^3
  • 1 <= pattern.length <= n
  • 1 <= targetIndices.length <= n
  • targetIndices is sorted in ascending order and its values are distinct
  • 0 <= targetIndices[i] <= n - 1
  • source and pattern consist only of lowercase English letters
  • pattern is a subsequence of source

Hints for Find Maximum Removals From Source String

  1. Hint 1

    Flip the question: the characters you keep must still contain pattern as a subsequence. Every target index you do not use for matching can be removed.

  2. Hint 2

    So you want to match pattern inside source while using as few target indices as possible. Think of an LCS-style DP over (i, j) = first i characters of source, first j of pattern.

  3. Hint 3

    dp[i][j] = most removable target indices among the first i characters while matching the first j pattern characters: skip source[i - 1] (gain 1 if it is a target) or, if it equals pattern[j - 1], use it for the match.

How to solve Find Maximum Removals From Source String

Removing characters is safe exactly when the remaining characters still embed pattern. So pick one embedding of pattern that touches as few target indices as possible; every other target index can be removed. A subsequence DP finds that embedding.

Approach

  1. Mark which indices of source are targets.
  2. Let dp[j] be the maximum number of removable targets so far while having matched pattern[0..j); start with dp[0] = 0 and dp[j] = -∞ for j > 0.
  3. For each index i of source (with t = 1 if i is a target), update j from m down to 1: dp[j] = max(dp[j] + t, dp[j - 1] if source[i] == pattern[j - 1]); then dp[0] += t.
  4. Return dp[m].

Why it works

Each character of source is either used to match the next pattern character (so it must stay) or not used (so it may be removed if it is a target, and removing it never hurts). Any set of removals that keeps pattern as a subsequence corresponds to an embedding avoiding the removed indices, and the DP maximises the unused targets over all embeddings.

Complexity

  • Time — O(n · m)
  • Space — O(m)

Pitfalls

  • Updating j upwards would let one character match two pattern positions — go from m down to 1.
  • Greedily matching pattern as early as possible is wrong: it may use target indices that a later match would have avoided.

Reference solution

Python

from typing import List

def maxRemovals(source: str, pattern: str, targetIndices: List[int]) -> int:
    n, m = len(source), len(pattern)
    is_target = [0] * n
    for i in targetIndices:
        is_target[i] = 1
    NEG = -10**9
    dp = [0] + [NEG] * m
    for i in range(n):
        t = is_target[i]
        c = source[i]
        for j in range(m, 0, -1):
            best = dp[j] + t
            if c == pattern[j - 1] and dp[j - 1] > best:
                best = dp[j - 1]
            dp[j] = best
        dp[0] += t
    return dp[m]

Java

public static int maxRemovals(String source, String pattern, int[] targetIndices) {
    int n = source.length(), m = pattern.length();
    int[] isTarget = new int[n];
    for (int i : targetIndices) isTarget[i] = 1;
    final int NEG = -1000000000;
    int[] dp = new int[m + 1];
    Arrays.fill(dp, NEG);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        int t = isTarget[i];
        char c = source.charAt(i);
        for (int j = m; j >= 1; j--) {
            int best = dp[j] + t;
            if (c == pattern.charAt(j - 1) && dp[j - 1] > best) best = dp[j - 1];
            dp[j] = best;
        }
        dp[0] += t;
    }
    return dp[m];
}

C++

int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
    int n = source.size(), m = pattern.size();
    vector<int> isTarget(n, 0);
    for (int i : targetIndices) isTarget[i] = 1;
    const int NEG = -1000000000;
    vector<int> dp(m + 1, NEG);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        int t = isTarget[i];
        for (int j = m; j >= 1; j--) {
            int best = dp[j] + t;
            if (source[i] == pattern[j - 1] && dp[j - 1] > best) best = dp[j - 1];
            dp[j] = best;
        }
        dp[0] += t;
    }
    return dp[m];
}

JavaScript

var maxRemovals = function(source, pattern, targetIndices) {
    var n = source.length, m = pattern.length;
    var isTarget = new Array(n).fill(0);
    for (var a = 0; a < targetIndices.length; a++) isTarget[targetIndices[a]] = 1;
    var NEG = -1000000000;
    var dp = [0];
    for (var j = 1; j <= m; j++) dp.push(NEG);
    for (var i = 0; i < n; i++) {
        var t = isTarget[i], c = source.charAt(i);
        for (var k = m; k >= 1; k--) {
            var best = dp[k] + t;
            if (c === pattern.charAt(k - 1) && dp[k - 1] > best) best = dp[k - 1];
            dp[k] = best;
        }
        dp[0] += t;
    }
    return dp[m];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings