题目描述

给你一个长度为 n 的字符串 source，一个字符串 pattern 且它是 source 的 子序列，和一个 有序 整数数组 targetIndices，整数数组中的元素是 [0, n - 1] 中 互不相同 的数字。

定义一次 操作 为删除 source 中下标在 idx 的一个字符，且需要满足：

• idx 是 targetIndices 中的一个元素。
• 删除字符后，pattern 仍然是 source 的一个 子序列。

执行操作后 不会 改变字符在 source 中的下标位置。比方说，如果从 "acb" 中删除 'c'，下标为 2 的字符仍然是 'b'。

请你返回 最多 可以进行多少次删除操作。

子序列指的是在原字符串里删除若干个（也可以不删除）字符后，不改变顺序地连接剩余字符得到的字符串。

样例

输入：source = "abbaa", pattern = "aba", targetIndices = [0,1,2]

输出：1

解释：

不能删除 source[0]，但我们可以执行以下两个操作之一：

删除 source[1]，source 变为 "a_baa" 。
删除 source[2]，source 变为 "ab_aa" 。

输入：source = "bcda", pattern = "d", targetIndices = [0,3]

输出：2

解释：

进行两次操作，删除 source[0] 和 source[3] 。

输入：source = "dda", pattern = "dda", targetIndices = [0,1,2]

输出：0

解释：

不能在 source 中删除任何字符。

输入：source = "yeyeykyded", pattern = "yeyyd", targetIndices = [0,2,3,4]

输出：2

解释：

进行两次操作，删除 source[2] 和 source[3] 。

限制

• 1 <= n == source.length <= 3 * 10^3
• 1 <= pattern.length <= n
• 1 <= targetIndices.length <= n
• targetIndices 是一个升序数组。
• 输入保证 targetIndices 包含的元素在 [0, n - 1] 中且互不相同。
• source 和 pattern 只包含小写英文字母。
• 输入保证 pattern 是 source 的一个子序列。

算法

(动态规划) $O(nm)$

1. 设状态 $f(i, j)$ 表示遍历了 source 的前 $i$ 个字符，匹配到 pattern 的前 $j$ 个字符时的最大得分。其中，没有 被 $targetIndices$ 标记的位置的分数为 $1$，否则为 $0$。
2. 初始时，$f(i, 0) = 0$，其余为负无穷待定。
3. 转移时，对于 $f(i, j)$，可以不使用第 $i$ 个字符匹配，则转移 $f(i, j) = f(i - 1, j)$。如果 $source(i) = pattern(j)$，则可以转移 $f(i, j) = \max(f(i, j), f(i - 1, j - 1) + w)$。其中 $w$ 就是第 $i$ 个位置的分数。
4. 最终，通过 $f(n, m)$ 的最大得分，可以知道最少都需要有 $m - f(n, m)$ 个字符在被 $targetIndices$ 标记的位置上。所以答案为 $targetIndices.size() - (m - f(n, m))$。
5. 由于第一维仅与前一个状态相关，所以可以省略掉第一维的状态表示，第二维通过倒序枚举进行转移。

时间复杂度

• 动态规划的状态数为 $O(nm)$，转移时间为常数，故时间复杂度为 $O(nm)$。

空间复杂度

• 优化状态表示后，需要 $O(m)$ 的额外空间存储状态。

C++ 代码

class Solution {
public:
    int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
        const int n = source.size(), m = pattern.size(), t = targetIndices.size();
        vector<int> f(m + 1, INT_MIN);

        f[0] = 0;

        for (int i = 0, k = 0; i < n; i++) {
            if (k < t && i > targetIndices[k])
                ++k;

            int w = k == t || i < targetIndices[k];

            for (int j = m; j >= 1; j--)
                if (source[i] == pattern[j - 1])
                    f[j] = max(f[j], f[j - 1] + w);
        }

        return t - (m - f[m]);
    }
};