🔗 🟡 2486. Append Characters to String to Make Subsequence 1363

tags: `Weekly Contest 321` `貪心(Greedy)` `雙指標(Two Pointers)` `字串(String)`

題意

給定兩個由小寫字母組成的字串 $s$ 和 $t$ 。

透過向 $s$ 末尾增加字元的方式使 $t$ 變成 $s$ 的一個 子序列(subsequence)，返回需要追加的最少字符數。

子序列(subsequence) 是一個可以由其他字串刪除部分（或不刪除）字元，但不改變剩下字元順序，所得到的字串。

思路：貪心(Greedy) + 雙指標(Two Pointers)

這題本質上是找到最大的 $j$ ，使得 $t[:j]$ 是 $s$ 的子序列。

首先基於貪心(Greedy) 思路思考，我們可以發現，對於 $t$ 的第 $j$ 個字元，若其出現在 $s$ 中，則出現的位置越早越好，因為這樣在後續的匹配過程中有更多的空間，如此 $t$ 的第 $j+1$ 個字元有更大的可能在 $s$ 中。

因此我們可以使用雙指針的方式來解決這個問題，令 $i$ 和 $j$ 分別指向 $s$ 和 $t$ 的開頭，當 $s[i] == t[j]$ 時，則 $j$ 往後移動，否則 $i$ 往後移動。到 $i$ 或 $j$ 超出範圍，此時 $t[:j]$ 為 $s$ 的子序列，需要補上的字元數即為 $m - j$ 。

複雜度分析

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

class Solution {
public:
    int appendCharacters(string s, string t) {
        int n = s.size(), m = t.size();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s[i] == t[j]) j++;
            i++;
        }
        return m - j;
    }
};