最少得分子序列

题目

6357. 最少得分子序列

---

给你两个字符串 s 和 t 。

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

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

• 令 left 为删除字符中的最小下标。
• 令 right 为删除字符中的最大下标。

字符串的得分为 right - left + 1 。

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

一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "***a***b***c***d***e***" 的子序列，但是 "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 为删除字符中的最大下标。
删除left到right中所有字符，得分仍然相同，且更容易让t成为s的子序列。

所以我们将题目转化为删除t最小的子串使得成为s的子序列。

t[:left-1]在s中的子序列应该越靠前越好。
t[:right+1]在s中的子序列应该越靠后越好。

我们可以O(n)分别预处理出
l[i] t中前i个字符在s中最靠前的子序列位置（子序列最后一个字符在s中的位置）
l[i] t中后i个字符在s中最靠后的子序列位置（子序列第一个字符在s中的位置）
若l[x-1]<r[y+1]，则说明删除子串[x,y]可以成为子序列。

f(x) 为在t中删除长度为x的子串，能否成为s的子序列。
显然x越大越有可能成为。

因此可以二分找到第一个满足f(x) = 1的x。

每次二分时可以通过滑动窗口来判断。

代码

class Solution {
public:
    int minimumScore(string s, string t) {
        int n = t.size(), m = s.size();
        t = "0"+t+"0";
        vector<int> l(n+2, -1), r(n+2, m); //l[i] 为t[1:i]为s中子序列，t[i]在s中最小位置。
        for (int i=1, p=0; i<=n; i++) {
            while (p<m && t[i] != s[p]) p++;
            l[i] = p++;
        }
        for (int i=n, p=m-1; i>0; i--) {
            while (p>=0 && t[i] != s[p]) p--;
            r[i] = p--;
        }
        int low = 0, upp = n;
        while (low < upp) {
            int mid = low+upp>>1;
            int ok = 0;
            for (int i=mid+1; i<=n+1; i++) {
                if (l[i-mid-1] < r[i]) ok = 1;
            }
            if (ok) {
                upp = mid;
            } else {
                low = mid+1;
            }
        }
        return upp;
    }
};