追加字符以获得子序列 图解题解

追加最少字符让 t 成为 s 的子序列，求几个

给两个只含小写字母的字符串 s 和 t，允许往 s 的末尾接上任意字符，问最少接几个，能让 t 成为 s 的子序列。子序列 = 保持相对顺序、从原串里删掉若干字符剩下的串，中间可以跳、不必挨着。题面例子：s=coaching、t=coding 答案 4；s=abcde、t=a 答案 0；s=z、t=abcde 答案 5。

为什么算两串长度差就交卷会错

容易把答案当成两个串的长度差，或者以为要在 s 里找出 t 这一整段连续子串。两条都不对：追加数只跟 t 里「在 s 中对不上」的字符有关，s 再长、缺 t 要的字符也白搭；而子序列允许中间跳字符，不要求连续。真去枚举 t 塞进 s 的每种嵌法硬试，方案多到指数级、根本扫不完。

顺着 t 走一遍、能对上就前进

真正省力的办法是盯着 t 的进度：拿一个指针 j 记「t 已顺序对上到第几位」，从头遍历 s。每看 s 的一个字符，只有它正好等于当前要找的 t[j] 时，才说明 t 这一位在 s 里落实了，j 挪一格去找下一位；对不上就跳过这个 s 字符，j 原地不动。这是子序列匹配的标准双指针，并贪心让每个 t 字符尽早对上——选最靠前的合法位置，不挡后面字符的机会，匹配到的位数只多不少。

扫完 s 后 j 停在哪，尾巴为什么就是要追加的

s 扫到头时，j 停的数值就是 t 从开头起能被顺序对上的最长前缀长度。前面这 j 位已稳稳嵌在 s 里，剩下 t 从第 j 位往后那段尾巴，在现有 s 里再找不到落点。可 t 的相对顺序不能改，这段尾巴只能原样接到 s 末尾，正好 |t| 减 j 个。所以扫完直接返回 len(t) 减 j。这也说清两条边界：t 本就是 s 的子序列时 j 走到底、答案 0；一个字符都对不上时 j 停在 0、答案就是整个 |t|。

顺着 coaching 和 coding 走一遍

记 n=len(t)=6，匹配指针 j 从 0 出发，逐个扫 s=coaching。s[0]=c 等于 t[0]=c，j 进到 1；s[1]=o 等于 t[1]=o，j 进到 2；s[2]=a 要找 t[2]=d，不等、跳过，j 停 2；后面 c、h、i、n、g 一路都不是 d，j 始终卡在 2。s 扫完时 j 落在 2，返回 6 减 2 得 4，正是往末尾追加 ding 这四个字符。

另两组：s=z、t=abcde，z 不等于 t[0]=a，j 一直是 0，返回 5 减 0 得 5，整个 t 都得追加；反过来 s=abcde、t=a，第一个 a 就对上 t[0]，j 变 1，返回 1 减 1 得 0，本来就是子序列，一个都不用加。

一趟线性扫，这几处最容易写岔

时间 O(|s|)：s 扫一遍、每个字符一次常数比较，j 最多前进 |t| 次；空间 O(1)，只用 j 和一个长度变量。几处手滑得防：匹配不上时若也让 j 前进，等于跳过没对上的字符、答案算小；相等时忘了继续挪 s 的下标，遇到 t 里连续相同字符会拿同一个 s 字符重复顶两位；还有别把答案写成 len(s) 减 len(t)，跟 s 的长度无关。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int appendCharacters(string s, string t) {
        int n = t.length(), j = 0;
        for (int i = 0; i < s.size() && j < n; ++i) {
            if (s[i] == t[j]) {
                ++j;
            }
        }
        return n - j;
    }
};

Java

import java.util.*;
class Solution {
    public int appendCharacters(String s, String t) {
        int n = t.length(), j = 0;
        for (int i = 0; i < s.length() && j < n; ++i) {
            if (s.charAt(i) == t.charAt(j)) {
                ++j;
            }
        }
        return n - j;
    }
}