LC-6357.最少得分子序列

题目描述

leetcode 困难题

给你两个字符串 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 是能得到的最小得分。

提示1：

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

前后缀分解 + 双指针

注意到得分只取决于删除的最大/最小下标，那么我们不妨将 $left, right$ 之间的元素全部删除，这样既不影响得分，$t$ 也依旧是 $s$ 的一个子序列。也就是说此时除了 $t[left…right]$ 区间的元素，$t$ 中剩余的元素都必须与 $s$ 的子序列匹配。

这样一来我们就可以进行前后缀分解，设 $i$ 为 $s$ 的某个下标

• $pre[i]$ 表示 $s[0…i]$ 子序列能够在 $t$ 中匹配到的最长前缀
• $suf[i]$ 表示 $s[i…n]$ 子序列能够在 $t$ 中匹配到的最长后缀

那么显然答案就为 $max( suf[i + 1] - 1 - (pre[i] + 1) + 1 )$ 。

接下来考虑如何维护 $pre$ 和 $suf$ ，可以通过双指针进行维护。以 $pre$ 为例，初始时指针 $i、j$ 分别指向 $s、t$ 的 $0$ 下标处，匹配过程中每次 $i$ 往后移动一位，而当 $s[i] == t[j]$ 时，说明匹配成功，$j$ 往后移动一位，每次更新 $pre[i]$ 为 $j - 1$ 即可。

class Solution {
    public int minimumScore(String s, String t) {
        int n = s.length();
        int m = t.length();
        int[] pre = new int[n];
        for(int i = 0, j = 0; i < n && j < m; i++){   
            if(s.charAt(i) == t.charAt(j)){
                j++;
            }
            pre[i] = j - 1;
        }
        if(pre[n - 1] == m - 1){
            return 0;
        }
        int[] suf = new int[n + 1];
        for(int i = n - 1, j = m - 1; i >= 0 && j >= 0; i--){ 
            if(s.charAt(i) == t.charAt(j)){
                j--;
            }
            suf[i] = j + 1;
        }
        int ans = suf[0] - 1 - (-1 + 1) + 1; // i.e. suf[0]
        suf[n] = m;
        for(int i = 0; i < n; i++){
            ans = Math.min(ans, suf[i + 1] - 1 - (pre[i] + 1) + 1); // i.e. suf[i + 1] - pre[i] - 1
        }
        return Math.max(ans, 0);
    }
}