LeetCode 2565.最少得分子序列

给你两个字符串 s 和 t 。

你可以从字符串 t 中删除任意数目的字符。

如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：

令 left 为删除字符中的最小下标。
令 right 为删除字符中的最大下标。
字符串的得分为 right - left + 1 。

请你返回使 t 成为 s 子序列的最小得分。

一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 “ace” 是 “abcde” 的子序列，但是 “aec” 不是）。

示例 1：

输入：s = “abacaba”, t = “bzaa”
输出：1
解释：这个例子中，我们删除下标 1 处的字符 “z” （下标从 0 开始）。
字符串 t 变为 “baa” ，它是字符串 “abacaba” 的子序列，得分为 1 - 1 + 1 = 1 。
1 是能得到的最小得分。
示例 2：

输入：s = “cde”, t = “xyz”
输出：3
解释：这个例子中，我们将下标为 0， 1 和 2 处的字符 “x” ，“y” 和 “z” 删除（下标从 0 开始）。
字符串变成 “” ，它是字符串 “cde” 的子序列，得分为 2 - 0 + 1 = 3 。
3 是能得到的最小得分。

提示：

1 <= s.length, t.length <= 10${}^5$
s 和 t 都只包含小写英文字母。

对于我们要删除的下标，left和right之间的字符可以全部删去，因为越删除，t就越可能成为s的子序列。删除子串后，剩下部分是t的一个前缀和一个后缀，我们可以找到t的后缀能匹配的最长s后缀，可以用suf数组记录下来s的每个下标对应的t中能匹配到的最长后缀，前缀同理，然后找出能使t成为s子序列的最小差值：

class Solution {
public:
    int minimumScore(string s, string t) {
        int sSize = s.size();
        int tSize = t.size();

        int sIdx = sSize - 1;
        int tIdx = tSize - 1;

        // suf保存s的下标最多能匹配到t中哪个后缀
        vector<int> suf(sSize + 1);
        suf[sSize] = tSize;

        while (sIdx >= 0 && tIdx >= 0) {
            if (s[sIdx] == t[tIdx]) {
                --tIdx;
            }

            // 最多能匹配到tIdx+1到t的结尾
            suf[sIdx] = tIdx + 1;
            --sIdx;
        }

        // 如果t匹配完了，说明t本身就是s的子序列
        if (tIdx < 0) {
            return 0;
        }

        // 补全剩下的suf数组
        while (sIdx >= 0) {
            suf[sIdx] = tIdx + 1;
            --sIdx;
        }

        // 初始化为删除t[0:suf[0]]的情况
        int ans = suf[0];
        
        sIdx = 0;
        tIdx = 0;

        while (sIdx < sSize && tIdx < tSize) {
            if (s[sIdx] == t[tIdx]) {
                ++tIdx;
            }

            // 找出最小得分
            // suf[sIdx + 1]是s的下一个下标对应的能匹配的最小right
            // tIdx - 1是s的当前下标对应的能匹配的最大left
            // 能删除的就是(left, right)
            ans = min(ans, suf[sIdx + 1] - (tIdx - 1) - 1);

            ++sIdx;
        }

        return ans;
    }
};

如果s的长度为n，则此算法时间复杂度为O(n)，空间复杂度为O(n)。