LeetCode 题解工作台
最少得分子序列
给你两个字符串 s 和 t 。 你可以从字符串 t 中删除任意数目的字符。 如果没有从字符串 t 中删除字符，那么得分为 0 ，否则： 令 left 为删除字符中的最小下标。 令 right 为删除字符中的最大下标。 字符串的得分为 right - left + 1 。 请你返回使 t 成为 s 子…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
根据题目我们知道，删除字符的下标范围是 `[left, right]`，最优的做法一定是删除 `[left, right]` 范围内的所有字符。也就是说，我们要删除字符串 中的一个子串，使得字符串 的剩余前缀可以匹配字符串 的前缀，字符串 的剩余后缀可以匹配字符串 的后缀，且字符串 的前后缀不相交。注意，这里的匹配指的是子序列匹配。 因此，我们可以先预处理得到数组 和 ，其中 表示…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你两个字符串 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 <= 105s和t都只包含小写英文字母。
解题思路
方法一：前后缀预处理 + 二分查找
根据题目我们知道，删除字符的下标范围是 [left, right]，最优的做法一定是删除 [left, right] 范围内的所有字符。也就是说，我们要删除字符串 中的一个子串，使得字符串 的剩余前缀可以匹配字符串 的前缀，字符串 的剩余后缀可以匹配字符串 的后缀，且字符串 的前后缀不相交。注意，这里的匹配指的是子序列匹配。
因此，我们可以先预处理得到数组 和 ，其中 表示字符串 的前缀 中，最少与字符串前 个字符匹配；同理 表示字符串 的后缀 中，最多与字符串后 个字符匹配。
而删除字符的长度具备单调性，如果删除长度为 的字符串后，满足条件，那么删除长度为 的字符串也一定满足条件。因此，我们可以使用二分查找的方法，找到最小的满足条件的长度。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def minimumScore(self, s: str, t: str) -> int:
def check(x):
for k in range(n):
i, j = k - 1, k + x
l = f[i] if i >= 0 else -1
r = g[j] if j < n else m + 1
if l < r:
return True
return False
m, n = len(s), len(t)
f = [inf] * n
g = [-1] * n
i, j = 0, 0
while i < m and j < n:
if s[i] == t[j]:
f[j] = i
j += 1
i += 1
i, j = m - 1, n - 1
while i >= 0 and j >= 0:
if s[i] == t[j]:
g[j] = i
j -= 1
i -= 1
return bisect_left(range(n + 1), True, key=check)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexities depend on the specific implementation of binary search and two-pointer techniques. In the best case, the approach achieves an optimal O(log(n) * m) complexity, where n is the length of string s and m is the length of string t. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate's understanding of binary search over valid answer space.
- question_mark
Ability to implement and use two-pointer techniques to validate subsequences.
- question_mark
Proficiency in balancing efficiency with correctness when solving string manipulation problems.
常见陷阱
外企场景- error
Over-complicating the subsequence check, resulting in inefficient solutions.
- error
Misusing binary search bounds, leading to incorrect results.
- error
Failing to correctly update pointers during the subsequence validation.
进阶变体
外企场景- arrow_right_alt
Consider variations where certain characters are already removed from t.
- arrow_right_alt
What if both strings are sorted, and additional optimizations can be applied?
- arrow_right_alt
Explore cases where the subsequence check isn't strictly left-to-right.