最少得分子序列

标签: 双指针 字符串 二分查找

难度: Hard

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

Submission

运行时间: 87 ms

内存: 20.2 MB

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

Explain

该题解采用了一种双指针和后缀数组的混合策略，来确定最小得分。首先，从后向前遍历字符串s，同时使用指针j跟踪字符串t，寻找t作为s的子序列的最后一个字符的位置。这个位置存储在suf数组中，suf[i]表示s从i开始，t需要删除到哪个位置才能成为s的子序列。然后，从前向后遍历字符串s，同时更新指针j来检查s的每个字符是否与t的当前字符匹配，如果匹配，则移动j。对于每个匹配，计算得分suf[i + 1] - j，这是当前i的最小得分。最后，返回所有可能得分中的最小值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minimumScore(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        suf = [m] * (n + 1)  # 后缀数组，记录t作为s的子序列需要删除到哪个位置
        j = m - 1
        for i in range(n - 1, -1, -1):
            if j >= 0 and s[i] == t[j]:
                j -= 1  # s[i]匹配t[j], j向左移
            suf[i] = j + 1  # 记录t需要删除到的位置
        ans = suf[0]  # 初始化最小得分
        if ans == 0: return 0  # 如果无需删除，得分为0
        j = 0
        for i, c in enumerate(s):
            if c == t[j]:  # 如果s[i]匹配t[j]
                j += 1  # j向右移动
                ans = min(ans, suf[i + 1] - j)  # 计算得分并更新最小值
        return ans

Explore

在题解中，后缀数组suf用于记录对于字符串s中的每个位置i，字符串t要成为s的子序列，需要删除到的位置。具体来说，suf[i]存储的是字符串t的索引位置，表示从t的这个位置往前（包括此位置），所有字符都已经在s的索引i及之前找到匹配。这样，suf数组帮助我们理解为了让t成为s从位置i开始的子序列，t需要保留哪些字符，从而可以计算出需要删除的字符数量。通过这种方式，我们可以针对每个s的位置，快速得到t需要调整的程度，进而计算出每个位置的得分。

选择反向遍历s字符串来构建suf数组的原因是，这样可以更自然地处理t的字符与s的匹配顺序。当我们从s的末尾开始向前遍历时，我们逐渐构建t作为s子序列的可能性。这使我们能够在遇到匹配的字符时，逐步减小j的值（即t的索引），这能够保证t的这部分是s从当前i位置到末尾的有效子序列。如果我们从前向后遍历s，则每次匹配后处理t的剩余部分会变得复杂，因为我们需要不断更新和回溯t的索引位置，这在逻辑上和实现上都更为复杂。

在题解中，'suf[i + 1] - j'用于计算每个匹配位置的得分。这里，suf[i + 1]表示在字符串s的位置i+1及之后，t成为s的子序列需要删除t中字符到的位置。而j是当前匹配到的t的字符位置，表示t中前j个字符已经在s中找到了匹配。因此，suf[i + 1] - j实际上表示从t的第j个位置到suf[i + 1]的位置，t需要保留的字符数量，即s[i]位置处的得分。这个得分反映了在i位置匹配之后，为了保持t作为s的子序列，t需要做出的调整。