主題
題目連結：
題目意譯：
你被給定兩個字串 s 和 t。
你被允許來從字串 t 中移除任意數量的字元。
如果字串 t 中沒有字元被移除，則其分數為 0；反之，如果有被移除的字元：
令 left 為所有被移除的字元中索引值之最小值、
令 right 為所有被移除的字元中索引值之最小值。
則字串的分數為 right - left + 1。
回傳在使 t 變成 s 的一個子序列的情況下，最小可能的分數值。
一個字串的一個子序列為一個新的字串，其可由原始字串刪除若干個字元（可以不刪除任何一個）並不更動剩餘字元之間的相對順序而得（即，"ace" 是 "abcde" 的一個子序列；而 "aec" 則不是）。
限制：
1 ≦ s.length, t.length ≦ 10 ^ 5
s 和 t 只由小寫英文字母組成。
範例測資：
範例 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 開始）。
字串 t 變成 ""，其為字串 "cde" 的一個子序列而分數為 2 - 0 + 1 = 3。
可以證明 3 是最小我們可以得到的分數。
解題思維：
假設 L 和 R 是某個最佳解的 left 和 right 之值。可以看到這代表著回到原本的字串 t 中把 t[L] ～ t[R] 的部分全部移除不會比最佳解差（原本的可能 t[L] ～ t[R] 之間有剩餘的字元）。
因此我們加上這個「能移除就全部移除」的條件之後，最佳解只會有以下五種：
一：t 的字元全部都被移除；
二：t 的字元全部保留；
三：剩下 t 的某個前綴；
四：剩下 t 的某個後綴；
五：剩下 t 的某個前綴 + 某個後綴。
情況一可以用這題的方式來檢查 t 是不是就是 s 的一個子序列；而情況二代表著 t 的任何一個字元都沒有出現在 s 中。
而剩下的情況可以看到這些前綴或後綴都代表著 s 中存在某個前綴（後綴）子字串使得這些 t 的前綴（後綴）是這個子字串的子序列。
所以可以看到我們能用某個字元 s[i] 將 s 分成 s[0] ～ s[i] 這個前綴（稱其為 s1）以及 s[i + 1] ～ s[s.length - 1] 這個後綴（稱其為 s2）。而 s1 可以對應到 t[0] ～ t[X - 1]，其中 X 盡可能地大；s2 可以對應到 t[Y + 1] ～ t[t.length - 1]，其中 Y 盡可能地小。
如果 X > Y，則代表 t 可以整個保留；而如果 X ≦ Y，則代表我們可以把 t[X] ～ t[Y] 這個部分整個刪掉，這會使得剩下的字元將會是 s 的一個子序列。因此分數會是 Y - X + 1。
（實際上情況一可以被包在這裡，畢竟 t 是自身的前綴以及後綴；情況二也是同理，因為空字串可以視為是前綴或後綴。）
所以我們可以把所有 s[i] 對應的分數找出來，求最小值即是所求。
那要怎麼求這些 X 、 Y 值？利用原本我們處理情況一的方式即可。原本我們從左至右掃過整個 s 之後，最後會停在 t 中的某個位置 X。如果 X == t.length，則代表 t 是 s 的子序列；反之，則 t[0] ～ t[X - 1] 這個前綴（如果 X == 0，則此為空字串）是 s 的一個子序列。
此時可以看到我們實際上找到了 s[s.length - 1] 的 X 值以及 Y 值（此時 Y == t.length，代表沒有後綴可以匹配）。而我們可以往回推得 s[s.length - 2] 、 s[s.length - 3] 等位置的 X 、 Y 值（方式跟原本檢查子序列的方法類似，只是現在 Y 代表著從 t 的結尾開始配對、而 X 則是會漸漸地往左退）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
