LeetCode 题解工作台
追加字符以获得子序列
给你两个仅由小写英文字母组成的字符串 s 和 t 。 现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。 子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。 示例 1： 输入： s = "coaching", t …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
我们定义两个指针 和 ，分别指向字符串 和 的首字符。遍历字符串 ，如果 $s[i] = t[j]$，则将 向后移动一位。最终返回 $n - j$，其中 是字符串 的长度。 时间复杂度 $(m + n)$，其中 和 分别是字符串 和 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你两个仅由小写英文字母组成的字符串 s 和 t 。
现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。
子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。
示例 1：
输入：s = "coaching", t = "coding"
输出：4
解释：向 s 末尾追加字符串 "ding" ，s = "coachingding" 。
现在，t 是 s ("coachingding") 的一个子序列。
可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。
示例 2：
输入：s = "abcde", t = "a"
输出：0
解释：t 已经是 s ("abcde") 的一个子序列。
示例 3：
输入：s = "z", t = "abcde"
输出：5
解释：向 s 末尾追加字符串 "abcde" ，s = "zabcde" 。
现在，t 是 s ("zabcde") 的一个子序列。
可以证明向 s 末尾追加任何 4 个字符都无法使 t 成为 s 的一个子序列。
提示：
1 <= s.length, t.length <= 105s和t仅由小写英文字母组成
解题思路
方法一：双指针
我们定义两个指针 和 ，分别指向字符串 和 的首字符。遍历字符串 ，如果 ，则将 向后移动一位。最终返回 ，其中 是字符串 的长度。
时间复杂度 ，其中 和 分别是字符串 和 的长度。空间复杂度 。
class Solution:
def appendCharacters(self, s: str, t: str) -> int:
n, j = len(t), 0
for c in s:
if j < n and c == t[j]:
j += 1
return n - j
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each character in s and t is visited at most once. Space complexity is O(1) because only pointers and counters are used, without additional data structures. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Asks about matching t's prefix efficiently within s using minimal extra characters.
- question_mark
Hints at using two pointers to avoid nested loops or repeated scans.
- question_mark
Checks understanding of subsequence invariants and linear time guarantees.
常见陷阱
外企场景- error
Attempting to check subsequences by generating all combinations of s and t, which is too slow.
- error
Resetting the t pointer incorrectly when a match fails, breaking the invariant.
- error
Over-appending characters without calculating the longest prefix of t already present in s.
进阶变体
外企场景- arrow_right_alt
Count minimal characters to prepend instead of append to make t a subsequence.
- arrow_right_alt
Modify s in-place with limited extra memory to achieve the subsequence.
- arrow_right_alt
Determine the minimum number of deletions from s to make t a subsequence.