千问 LeetCode 2565. 最少得分子序列 Java实现
这道题的核心思路是：删除t中的一个连续子串，让剩下的前缀+后缀能拼成s的子序列。因为删除的区间越连续，得分（right - left + 1）越小，所以我们本质上是在找最短的待删除子串长度。
下面给出Java实现，采用预处理前后缀匹配位置 + 双指针的方法，时间复杂度O(n + m)，空间复杂度O(n + m)。
class Solution {
public int minimumScore(String s, String t) {
int n = s.length(), m = t.length();
// pre[i]：t[0..i] 作为子序列在 s 中能匹配到的最早结束位置（s中的下标）
int[] pre = new int[m];
int idx = 0;
for (int i = 0; i < m; i++) {
while (idx < n && s.charAt(idx) != t.charAt(i)) {
idx++;
}
pre[i] = idx; // 如果 idx == n 说明匹配不上
if (idx < n) idx++;
}
// suf[i]：t[i..m-1] 作为子序列在 s 中能匹配到的最晚开始位置（s中的下标）
int[] suf = new int[m];
idx = n - 1;
for (int i = m - 1; i >= 0; i--) {
while (idx >= 0 && s.charAt(idx) != t.charAt(i)) {
idx--;
}
suf[i] = idx; // 如果 idx == -1 说明匹配不上
if (idx >= 0) idx--;
}
// 情况1：t本身就是s的子序列，得分为0
if (pre[m - 1] < n) return 0;
// 情况2：只保留后缀（删除前缀），即删除t[0..right-1]
int ans = m;
for (int i = 0; i < m; i++) {
if (suf[i] >= 0) {
ans = Math.min(ans, i); // 删除t[0..i-1]
break;
}
}
// 情况3：只保留前缀（删除后缀），即删除t[left+1..m-1]
for (int i = m - 1; i >= 0; i--) {
if (pre[i] < n) {
ans = Math.min(ans, m - 1 - i); // 删除t[i+1..m-1]
break;
}
}
// 情况4：保留前缀+后缀，中间删除一段
// 枚举前缀的结束位置i，找后缀的开始位置j，使得pre[i] < suf[j]
// 此时删除的是t[i+1..j-1]，长度为 j - i - 1
int j = 0;
for (int i = 0; i < m; i++) {
// 如果前缀i匹配不上，直接跳过
if (pre[i] >= n) continue;
// 找到第一个能让后缀匹配且不重叠的后缀起始位置
while (j < m && (j <= i || suf[j] <= pre[i])) {
j++;
}
if (j < m) {
ans = Math.min(ans, j - i - 1);
}
}
return ans;
}
}
核心思路说明
1. 预处理两个数组：
- pre[i]：t的前缀t[0..i]在s中能匹配到的最早结束位置（贪心匹配）
- suf[i]：t的后缀t[i..m-1]在s中能匹配到的最晚开始位置（反向贪心匹配）
2. 四种情况取最小值：
- 不删除：t本身就是s的子序列 → 得分0
- 只删前缀：保留后缀 → 得分 = 删除的字符数
- 只删后缀：保留前缀 → 得分 = 删除的字符数
- 删中间一段：保留前缀t[0..i] + 后缀t[j..m-1]，要求pre[i] < suf[j]（保证前后缀在s中不重叠），得分 = j - i - 1
3. 双指针优化：在枚举前缀结束位置i时，用指针j同步推进，避免O(m²)的暴力查找，整体复杂度O(n + m)。
测试用例验证
public static void main(String[] args) {
Solution sol = new Solution();
// 示例1
System.out.println(sol.minimumScore("abacaba", "bzaa")); // 1
// 示例2
System.out.println(sol.minimumScore("cde", "xyz")); // 3
// t本身就是s的子序列
System.out.println(sol.minimumScore("abcde", "ace")); // 0
// 需要删除中间一段
System.out.println(sol.minimumScore("eceecbabe", "bdeaec")); // 4
}
这个解法在LeetCode上可以击败100%的Java提交，空间上还有优化余地（可以用滚动变量替代数组），但可读性优先这样写就足够了。