2565-最少得分子序列

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你两个字符串 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 <= 105
  • s 和 t 都只包含小写英文字母。

提示 1

在 [\textit{left}, \textit{right}] 之间的字符，删除是不影响得分的，且删除后更有机会让剩余部分是 s 的子序列。

因此只需考虑删除的是 t 的子串，而不是子序列。

提示 2

删除子串后，剩余部分是 t 的一个前缀和一个后缀。

假设前缀匹配的是 s 的一个前缀 s[:i]，后缀匹配的是 s 的一个后缀 s[i:]。这里匹配指子序列匹配。

那么枚举 i，分别计算能够与 s[:i] 和 s[i:] 匹配的 t 的最长前缀和最长后缀，就知道要删除的子串的最小值了。这个技巧叫做「前后缀分解」。

提示 3

具体来说：

定义 pre}[i] 为 s[:i] 对应的 t 的最长前缀的结束下标。

定义 suf}[i] 为 s[i:] 对应的 t 的最长后缀的开始下标。

那么删除的子串就是从 pre}[i]+1 到 suf}[i]-1 这段，答案就是 suf}[i]-\textit{pre}[i]-1 的最小值。

代码实现时，可以先计算 suf，然后一边计算 pre，一边更新最小值，所以 pre 可以省略。

附：视频讲解

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minimumScore(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        suf = [m] * (n + 1)
        j = m - 1
        for i in range(n - 1, -1, -1):
            if j >= 0 and s[i] == t[j]:
                j -= 1
            suf[i] = j + 1
        ans = suf[0]  # 删除 t[:suf[0]]
        if ans == 0: return 0

        j = 0
        for i, c in enumerate(s):
            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列
                j += 1
                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minimumScore(String S, String T) {
        char[] s = S.toCharArray(), t = T.toCharArray();
        int n = s.length, m = t.length;
        var suf = new int[n + 1];
        suf[n] = m;
        for (int i = n - 1, j = m - 1; i >= 0; --i) {
            if (j >= 0 && s[i] == t[j]) --j;
            suf[i] = j + 1;
        }
        int ans = suf[0]; // 删除 t[:suf[0]]
        if (ans == 0) return 0;
        for (int i = 0, j = 0; i < n; ++i)
            if (s[i] == t[j]) // 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列
                ans = Math.min(ans, suf[i + 1] - ++j); // ++j 后，删除 t[j:suf[i+1]]
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumScore(string s, string t) {
        int n = s.length(), m = t.length(), suf[n + 1];
        suf[n] = m;
        for (int i = n - 1, j = m - 1; i >= 0; --i) {
            if (j >= 0 && s[i] == t[j]) --j;
            suf[i] = j + 1;
        }
        int ans = suf[0]; // 删除 t[:suf[0]]
        if (ans == 0) return 0;
        for (int i = 0, j = 0; i < n; ++i)
            if (s[i] == t[j]) // 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列
                ans = min(ans, suf[i + 1] - ++j); // ++j 后，删除 t[j:suf[i+1]]
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func minimumScore(s, t string) int {
	n, m := len(s), len(t)
	suf := make([]int, n+1)
	suf[n] = m
	for i, j := n-1, m-1; i >= 0; i-- {
		if j >= 0 && s[i] == t[j] {
			j--
		}
		suf[i] = j + 1
	}
	ans := suf[0] // 删除 t[:suf[0]]
	if ans == 0 {
		return 0
	}
	for i, j := 0, 0; i < n; i++ {
		if s[i] == t[j] { // 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列
			j++
			ans = min(ans, suf[i+1]-j) // 删除 t[j:suf[i+1]]
		}
	}
	return ans
}

func min(a, b int) int { if b < a { return b }; return a }

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 s 的长度。注意时间复杂度和 t 的长度无关。
  • 空间复杂度：O(n)。
 Comments
On this page
2565-最少得分子序列
  1. 提示 1
  2. 提示 2
  3. 提示 3
  4. 复杂度分析