3316. Find Maximum Removals From Source String

Description

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 * 10³
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.

Solutions

Solution 1: Dynamic Programming

We define \(f[i][j]\) to represent the maximum number of deletions in the first \(i\) characters of \(\textit{source}\) that match the first \(j\) characters of \(\textit{pattern}\). Initially, \(f[0][0] = 0\), and the rest \(f[i][j] = -\infty\).

For \(f[i][j]\), we have two choices:

We can skip the \(i\)-th character of \(\textit{source}\), in which case \(f[i][j] = f[i-1][j] + \text{int}(i-1 \in \textit{targetIndices})\);
If \(\textit{source}[i-1] = \textit{pattern}[j-1]\), we can match the \(i\)-th character of \(\textit{source}\), in which case \(f[i][j] = \max(f[i][j], f[i-1][j-1])\).

The final answer is \(f[m][n]\).

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Here, \(m\) and \(n\) are the lengths of \(\textit{source}\) and \(\textit{pattern}\), respectively.

Python3JavaC++GoTypeScript

class Solution:
    def maxRemovals(self, source: str, pattern: str, targetIndices: List[int]) -> int:
        m, n = len(source), len(pattern)
        f = [[-inf] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 0
        s = set(targetIndices)
        for i, c in enumerate(source, 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j] + int((i - 1) in s)
                if j and c == pattern[j - 1]:
                    f[i][j] = max(f[i][j], f[i - 1][j - 1])
        return f[m][n]

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];
    }
}

class Solution {
public:
    int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
        int m = source.length(), n = pattern.length();
        vector<vector<int>> f(m + 1, vector<int>(n + 1, INT_MIN / 2));
        f[0][0] = 0;

        vector<int> s(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[i - 1] == pattern[j - 1]) {
                    f[i][j] = max(f[i][j], f[i - 1][j - 1]);
                }
            }
        }

        return f[m][n];
    }
};

func maxRemovals(source string, pattern string, targetIndices []int) int {
    m, n := len(source), len(pattern)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
        for j := range f[i] {
            f[i][j] = -math.MaxInt32 / 2
        }
    }
    f[0][0] = 0

    s := make([]int, m)
    for _, i := range targetIndices {
        s[i] = 1
    }

    for i := 1; i <= m; i++ {
        for j := 0; j <= n; j++ {
            f[i][j] = f[i-1][j] + s[i-1]
            if j > 0 && source[i-1] == pattern[j-1] {
                f[i][j] = max(f[i][j], f[i-1][j-1])
            }
        }
    }

    return f[m][n]
}

function maxRemovals(source: string, pattern: string, targetIndices: number[]): number {
    const m = source.length;
    const n = pattern.length;
    const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(-Infinity));
    f[0][0] = 0;

    const s = Array(m).fill(0);
    for (const i of targetIndices) {
        s[i] = 1;
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            f[i][j] = f[i - 1][j] + s[i - 1];
            if (j > 0 && source[i - 1] === pattern[j - 1]) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j - 1]);
            }
        }
    }

    return f[m][n];
}

3316. Find Maximum Removals From Source String

Description

Solutions

Solution 1: Dynamic Programming

Comments