2486-追加字符以获得子序列

给你两个仅由小写英文字母组成的字符串 s 和 t 。

现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。

子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。

示例 1：

**输入：** s = "coaching", t = "coding"
**输出：** 4
**解释：** 向 s 末尾追加字符串 "ding" ，s = "coachingding" 。
现在，t 是 s (" _ **co**_ aching _ **ding**_ ") 的一个子序列。
可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。

示例 2：

**输入：** s = "abcde", t = "a"
**输出：** 0
**解释：** t 已经是 s (" _ **a**_ bcde") 的一个子序列。

示例 3：

**输入：** s = "z", t = "abcde"
**输出：** 5
**解释：** 向 s 末尾追加字符串 "abcde" ，s = "zabcde" 。
现在，t 是 s ("z _ **abcde**_ ") 的一个子序列。 
可以证明向 s 末尾追加任何 4 个字符都无法使 t 成为 s 的一个子序列。

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 仅由小写英文字母组成

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

贪心，双指针遍历 s 和 t，t[j] 应匹配 i 尽量小（但大于上一个的匹配的位置）的 s[i]。

第一种写法：

[sol1-Python3]

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        i, n = 0, len(s)
        for j, c in enumerate(t):
            while i < n and s[i] != t[j]: i += 1
            if i == n: return len(t) - j
            i += 1
        return 0

[sol1-Go]

func appendCharacters(s, t string) int {
	i, n := 0, len(s)
	for j := range t {
		for i < n && s[i] != t[j] {
			i++
		}
		if i == n {
			return len(t) - j
		}
		i++
	}
	return 0
}

第二种写法：

[sol2-Python3]

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        j, m = 0, len(t)
        for c in s:
            if c == t[j]:
                j += 1
                if j == m: return 0
        return m - j

[sol2-Go]

func appendCharacters(s, t string) int {
	j, m := 0, len(t)
	for _, c := range s {
		if byte(c) == t[j] { // s 的字符肯定匹配的是 t 的前缀
			j++
			if j == m {
				return 0
			}
		}
	}
	return m - j
}

复杂度分析

• 时间复杂度：O(n+m)，其中 n 为 s 的长度，m 为 t 的长度。
• 空间复杂度：O(1)，仅用到若干额外变量。