主題
題目連結：
題目意譯：
你被給定一個由小寫字母組成的字串 s，以及一整數 k。如果以下條件符合，則我們將稱呼一個字串 t 是理想的：
t 為 s 的一個子序列、
在 t 中，每兩個相鄰字母在字母表中位置值之絕對差小於等於 k。
回傳最長的理想字串之長度。
一個子序列為一個可以由另一字串刪除若干個或零個字元並使得剩餘字元相對順序不變而得到的字串。
注意到字母表順序並不是頭尾相連的。例如說，'a' 和 'z' 在字母表中相差 25，而不是 1。
限制：
1 ≦ s.length ≦ 10 ^ 5
0 ≦ k ≦ 25
s 由小寫英文字母組成。
範例測資：
範例 1：
輸入： s = "acfgbd", k = 2
輸出： 4
解釋： 最長的理想字串為 "acbd"。其長度為 4，因此回傳 4。
注意到 "acfgbd" 不理想，因為 'c' 和 'f' 在字母表中的差為 3。
範例 2：
輸入： s = "abcd", k = 3
輸出： 4
解釋： 最長的理想字串為 "abcd"。其長度為 4，因此回傳 4。
解題思維：
（令 n = s.length）
典型的動態規劃（Dynamic Programming，DP）之題型。
定義一個二維陣列 D，其中 D[i][j] 為前 i 個字元所組成的字串中以 j 這個字母作為結尾的理想字串最長長度為何。
因此其遞迴式為
D[0][j] = 0、
D[i][s[i - 1]] = max(D[i - 1][j] + 1)，其中 j 與 s[i - 1] 之絕對差小於等於 k、
D[i][j] = D[i - 1][j]，其中 j != s[i - 1]。
（其中 i > 0）
因此從 i = 1 開始按照上面的遞迴式算到 i = n 為止，D[n]['a'] 、 D[n]['b']、……中的最大值即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
