Find Maximum Removals From Source String

Problem

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.

Examples

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 * 10^3
• 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.

Solution

Method 1 – Binary Search with Subsequence Check

Intuition

We want to maximize the number of removals from source at indices in targetIndices such that pattern remains a subsequence. Since each removal is independent and the order of removals doesn't affect the result, we can use binary search to find the maximum number of removable indices.

Approach

1. Use binary search on the number of removals k (from 0 to len(targetIndices)).
2. For each k, mark the first k indices in targetIndices as removed.
3. Check if pattern is still a subsequence of the modified source:
   • Iterate through source, skipping removed indices, and try to match all characters of pattern in order.
4. If pattern is a subsequence, try a larger k; otherwise, try a smaller k.
5. Return the maximum k found.

Code

C++

class Solution {
public:
    int maximumRemovals(string source, string pattern, vector<int>& targetIndices) {
        int l = 0, r = targetIndices.size(), ans = 0;
        while (l <= r) {
            int mid = l + (r-l)/2;
            vector<bool> removed(source.size(), false);
            for (int i = 0; i < mid; ++i) removed[targetIndices[i]] = true;
            int j = 0;
            for (int i = 0; i < source.size() && j < pattern.size(); ++i) {
                if (!removed[i] && source[i] == pattern[j]) ++j;
            }
            if (j == pattern.size()) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

Go

func maximumRemovals(source string, pattern string, targetIndices []int) int {
    l, r, ans := 0, len(targetIndices), 0
    for l <= r {
        mid := l + (r-l)/2
        removed := make([]bool, len(source))
        for i := 0; i < mid; i++ {
            removed[targetIndices[i]] = true
        }
        j := 0
        for i := 0; i < len(source) && j < len(pattern); i++ {
            if !removed[i] && source[i] == pattern[j] {
                j++
            }
        }
        if j == len(pattern) {
            ans = mid
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return ans
}

Java

class Solution {
    public int maximumRemovals(String source, String pattern, int[] targetIndices) {
        int l = 0, r = targetIndices.length, ans = 0;
        while (l <= r) {
            int mid = l + (r-l)/2;
            boolean[] removed = new boolean[source.length()];
            for (int i = 0; i < mid; i++) removed[targetIndices[i]] = true;
            int j = 0;
            for (int i = 0; i < source.length() && j < pattern.length(); i++) {
                if (!removed[i] && source.charAt(i) == pattern.charAt(j)) j++;
            }
            if (j == pattern.length()) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun maximumRemovals(source: String, pattern: String, targetIndices: IntArray): Int {
        var l = 0; var r = targetIndices.size; var ans = 0
        while (l <= r) {
            val mid = l + (r-l)/2
            val removed = BooleanArray(source.length)
            for (i in 0 until mid) removed[targetIndices[i]] = true
            var j = 0
            for (i in 0 until source.length) {
                if (j < pattern.length && !removed[i] && source[i] == pattern[j]) j++
            }
            if (j == pattern.length) {
                ans = mid
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
        return ans
    }
}

Python

class Solution:
    def maximumRemovals(self, source: str, pattern: str, targetIndices: list[int]) -> int:
        def is_subseq(k: int) -> bool:
            removed = set(targetIndices[:k])
            j = 0
            for i, c in enumerate(source):
                if i in removed:
                    continue
                if j < len(pattern) and c == pattern[j]:
                    j += 1
            return j == len(pattern)
        l, r, ans = 0, len(targetIndices), 0
        while l <= r:
            mid = (l + r) // 2
            if is_subseq(mid):
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans

Rust

impl Solution {
    pub fn maximum_removals(source: String, pattern: String, target_indices: Vec<i32>) -> i32 {
        let s = source.as_bytes();
        let p = pattern.as_bytes();
        let n = s.len();
        let mut l = 0;
        let mut r = target_indices.len();
        let mut ans = 0;
        while l <= r {
            let mid = l + (r-l)/2;
            let mut removed = vec![false; n];
            for &idx in &target_indices[..mid.min(target_indices.len())] {
                removed[idx as usize] = true;
            }
            let mut j = 0;
            for i in 0..n {
                if removed[i] { continue; }
                if j < p.len() && s[i] == p[j] { j += 1; }
            }
            if j == p.len() {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        ans as i32
    }
}

TypeScript

class Solution {
    maximumRemovals(source: string, pattern: string, targetIndices: number[]): number {
        const isSubseq = (k: number): boolean => {
            const removed = new Set(targetIndices.slice(0, k));
            let j = 0;
            for (let i = 0; i < source.length; i++) {
                if (removed.has(i)) continue;
                if (j < pattern.length && source[i] === pattern[j]) j++;
            }
            return j === pattern.length;
        };
        let l = 0, r = targetIndices.length, ans = 0;
        while (l <= r) {
            const mid = Math.floor((l + r) / 2);
            if (isSubseq(mid)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log m), where n is the length of source and m is the length of targetIndices. Each subsequence check is O(n), and binary search is O(log m).
• 🧺 Space complexity: O(n), for the removed indices set or array.