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索引）。
字符串 t 变成 ""，它是字符串 "cde" 的子序列，分数为 2 - 0 + 1 = 3。
可以证明 3 是我们能达到的最小分数。

提示：

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

解题思路

这道题的关键思路是：我们要删除 t 中一段连续的子串，使得剩余部分能够成为 s 的子序列。

核心观察：

  1. 如果要删除字符，最优策略是删除一段连续的子串，这样分数就是子串的长度
  2. 保留的部分由两部分组成：t 的前缀和 t 的后缀
  3. 问题转化为：找到最短的中间段，使得删除后剩余的前缀+后缀能构成 s 的子序列

解法思路：

  1. 预处理阶段：计算两个数组

    • prefix[i]：表示 t[0...i-1] 作为 s 的子序列时，在 s 中的最小结束位置
    • suffix[j]：表示 t[j...n-1] 作为 s 的子序列时，在 s 中的最大开始位置

  2. 枚举删除区间：

    • 枚举所有可能的删除区间 [i, j]
    • 检查保留的前缀 t[0...i-1] 和后缀 t[j+1...n-1] 是否能构成 s 的子序列
    • 条件是：prefix[i] < suffix[j+1]（前缀在 s 中的结束位置要在后缀开始位置之前）

  3. 特殊情况处理：

    • 不删除任何字符（分数为0）
    • 只保留前缀或只保留后缀

时间复杂度为 O(n + m)，空间复杂度为 O(n)，其中 n 是 t 的长度，m 是 s 的长度。

代码实现

class Solution {
public:
    int minimumScore(string s, string t) {
        int m = s.length(), n = t.length();
        
        // prefix[i] = minimum ending position in s for subsequence t[0:i]
        vector<int> prefix(n + 1, m);
        prefix[0] = -1;
        
        int j = 0;
        for (int i = 0; i < n && j < m; i++) {
            while (j < m && s[j] != t[i]) j++;
            if (j < m) {
                prefix[i + 1] = j;
                j++;
            } else {
                break;
            }
        }
        
        // suffix[i] = maximum starting position in s for subsequence t[i:n]
        vector<int> suffix(n + 1, -1);
        suffix[n] = m;
        
        j = m - 1;
        for (int i = n - 1; i >= 0 && j >= 0; i--) {
            while (j >= 0 && s[j] != t[i]) j--;
            if (j >= 0) {
                suffix[i] = j;
                j--;
            } else {
                break;
            }
        }
        
        int result = n;  // worst case: remove all characters
        
        // Check if we can keep prefix t[0:i] and suffix t[j:n]
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                if (prefix[i] < suffix[j]) {
                    result = min(result, j - i);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def minimumScore(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        
        # prefix[i] = minimum ending position in s for subsequence t[0:i]
        prefix = [m] * (n + 1)
        prefix[0] = -1
        
        j = 0
        for i in range(n):
            while j < m and s[j] != t[i]:
                j += 1
            if j < m:
                prefix[i + 1] = j
                j += 1
            else:
                break
        
        # suffix[i] = maximum starting position in s for subsequence t[i:n]
        suffix = [-1] * (n + 1)
        suffix[n] = m
        
        j = m - 1
        for i in range(n - 1, -1, -1):
            while j >= 0 and s[j] != t[i]:
                j -= 1
            if j >= 0:
                suffix[i] = j
                j -= 1
            else:
                break
        
        result = n  # worst case: remove all characters
        
        # Check if we can keep prefix t[0:i] and suffix t[j:n]
        for i in range(n + 1):
            for j in range(i, n + 1):
                if prefix[i] < suffix[j]:
                    result = min(result, j - i)
        
        return result

public class Solution {
    public int MinimumScore(string s, string t) {
        int m = s.Length, n = t.Length;
        
        // prefix[i] = minimum ending position in s for subsequence t[0:i]
        int[] prefix = new int[n + 1];
        Array.Fill(prefix, m);
        prefix[0] = -1;
        
        int j = 0;
        for (int i = 0; i < n && j < m; i++) {
            while (j < m && s[j] != t[i]) j++;
            if (j < m) {
                prefix[i + 1] = j;
                j++;
            } else {
                break;
            }
        }
        
        // suffix[i] = maximum starting position in s for subsequence t[i:n]
        int[] suffix = new int[n + 1];
        Array.Fill(suffix, -1);
        suffix[n] = m;
        
        j = m - 1;
        for (int i = n - 1; i >= 0 && j >= 0; i--) {
            while (j >= 0 && s[j] != t[i]) j--;
            if (j >= 0) {
                suffix[i] = j;
                j--;
            } else {
                break;
            }
        }
        
        int result = n;  // worst case: remove all characters
        
        // Check if we can keep prefix t[0:i] and suffix t[j:n]
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                if (prefix[i] < suffix[j]) {
                    result = Math.Min(result, j - i);
                }
            }
        }
        
        return result;
    }
}

var minimumScore = function(s, t) {
    const m = s.length, n = t.length;
    
    // prefix[i] = minimum ending position in s for subsequence t[0:i]
    const prefix = new Array(n + 1).fill(m);
    prefix[0] = -1;
    
    let j = 0;
    for (let i = 0; i < n && j < m; i++) {
        while (j < m && s[j] !== t[i]) j++;
        if (j < m) {
            prefix[i + 1] = j;
            j++;
        } else {
            break;
        }
    }
    
    // suffix[i] = maximum starting position in s for subsequence t[i:n]
    const suffix = new Array(n + 1).fill(-1);
    suffix[n] = m;
    
    j = m - 1;
    for (let i = n - 1; i >= 0 && j >= 0; i--) {
        while (j >= 0 && s[j] !== t[i]) j--;
        if (j >= 0) {
            suffix[i] = j;
            j--;
        } else {
            break;
        }
    }
    
    let result = n;  // worst case: remove all characters
    
    // Check if we can keep prefix t[0:i] and suffix t[j:n]
    for (let i = 0; i <= n; i++) {
        for (let j = i; j <= n; j++) {
            if (prefix[i] < suffix[j]) {
                result = Math.min(result, j - i);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) 其中 n 是字符串 t 的长度。预处理前缀和后缀数组需要 O(m + n) 时间，枚举所有删除区间需要 O(n²) 时间
空间复杂度O(n) 存储前缀和后缀数组

相关题目