給你兩個字符串 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)。