主題
題目連結：
題目意譯：
一個密碼如果滿足以下所有條件，則視為是「強」密碼：
其至少有 6 個字元且最多 20 個字元、
其至少包含一個小寫字母、一個大寫字母以及一個數字、
其不包含連續三個重複字元（即 "Baaabb0" 是弱密碼，而 "Baaba0" 則是強的）。
給定一個字串 password，回傳最少所需的步驟來使密碼變強。
在一個步驟之中，你可以：
插入一個字元到 password 中、
從 password 中刪除一個字元、
把 password 中某一個字元替換成另一個字元。
限制：
1 ≦ password.length ≦ 50
password 由字母、數字、點 '.' 以及驚嘆號 '!' 所組成。
範例測資：
範例 1：
輸入： password = "a"
輸出： 5
範例 2：
輸入： password = "aA1"
輸出： 3
範例 3：
輸入： password = "1337C0d3"
輸出： 0
解題思維：
首先，我們定義三個變數 lower 、 upper 和 digit，分別代表著字串 password 分別有沒有小寫、大寫以及數字（用 0 代表「沒有」、 1 代表「有」）。
接著我們先來處理長度不足的情況，即 password.length < 6 時：
password.length ≦ 3，則不管 lower 、 upper 和 digit 實際上是什麼值，我們可以直接在 password 中加入大小寫以及數字（因為我們至少會加入 3 個字元）並將密碼長度補到 6 個字元長。因此最少只需要 6 - password.length 個步驟（即少幾個字元就補幾個）。
password.length == 4，由於只需要加入 2 個字元便可以把長度補到 6。因此如果 lower 、 upper 和 digit 其中至少一個是 1（可寫作 lower + upper + digit ≧ 1），則最少所需步驟即為 2；反之，則需要額外一個步驟來彌補 lower 、 upper 和 digit 都是 0 的情況，因此最少所需步驟為 3。總體可以簡化成 3 - min(1, lower + upper + digit)。
password.length == 5，與長度只有 4 的情況類似。如果 lower + upper + digit ≧ 2，則最少所需步驟為 1；若 lower + upper + digit == 1，則最少所需步驟為 2；最後若 lower + upper + digit == 0，則最少所需步驟為 3。總體可以簡化成 3 - min(2, lower + upper + digit)。
而上面的長度 4 和長度 5 之情況又可以進一步合併成為 3 - min(password.length - 3, lower + upper + digit)，而這個式子剛好也可以合併進長度 ≦ 3 的情況。因此範例程式碼中的此式即是由此而來。
並且以上情況完全不需要擔心會出現連續三個字元一樣。例如說，最糟的情況會是長度 5 且 password == "77777" 之類的情況。而此時只有 digit == 1，因此最少要補一個大寫、一個小寫，因此可以做到例如 "77A7a77" 等來把連續三個相同字元隔開。長度 4 就不用說了，本來就要至少補 2 個字元。因此連續三個相同字元在這邊一定可以被「順便」解決掉。
處理掉長度不足的情況之後，可以看到我們不可能會再次使用「新增字元」的操作了。因為現在要嘛長度足夠，要嘛太長，因此比起新增字元，刪除或是替換字元必定不會比較差。
接下來我們先不考慮長度不會過長，即 password.length ≦ 20 時的情況，直接掃過一次 password 來找出所有連續相同字元長度 ≧ 3 的片段。假設每一段的長度為 c1 、 c2 、……，此時我們可以看到要把這些連續相同的變成不連續或不相同的話，替換字元的操作不會比刪除字元差。
那最少需要幾次替換字元呢？可以看到片段長度如果是 3，則需要 1 次；長度如果是 4，則也只需要 1 次；長度 5，也是 1 次；長度 6，則是需要 2 次……以此類推。經過一番試驗後，應該不難看出規律是「L ÷ 3 取整數」，而這可寫作是 floor(L ÷ 3)，其中 L 為片段長度。
因此代表著現在找出的這些片段長度，c1 、 c2 、……，代表著我們至少需要 floor(c1 ÷ 3) + floor(c2 ÷ 3) + …… 次的替換字元。定義這個所需的替換次數為 C 次。
此時如果 C < (3 - (lower + upper + digit))（代表 password 中還缺哪幾種字元），則代表著在將 lower 、 upper 和 digit 藉由替換字元來彌補到都變成 1 的時候便可以「順便」把這些連續片段來「隔開」。因此最少所需步驟為 3 - (lower + upper - digit)；反之，則最少只需要 C 個步驟。
那如果長度太長，即 password.length > 20 呢？首先作法跟上面一樣，先掃過一次 password 來找出那些需要處理的連續片段之長度，一樣稱為 c1 、 c2 、 ……
此時由於長度太長，因此我們會至少需要 D = password.length - 20 次的刪除字元操作。而既然都要刪除字元了，便可以順便來消掉幾個連續片段，讓它們變短也好。
那怎樣刪比較好呢？
因為一個長度為 L 的片段會需要 floor(L ÷ 3) 次替換字元。因此如果 L 除以 3 的餘數是 0 的話，從中刪除一個字元將會把該片段的替換字元操作數直接減去 1。同理，L 除以 3 的餘數是 1 則需要刪除兩個字元才能使操作數減去 1；而餘數是 2 則需要三次。
也因此我們可以看出優先順序，即餘數小的要先優先處理。畢竟操作數會比較快降低。因此我們可以用一個優先佇列（Priority Queue）來維護這些「緊急度」。不過記得注意在處理這些連續片段時，一旦有刪過字元，其餘數會變化（因為長度變了），也連帶著「緊急度」也會變化。而且有可能刪著刪著長度就 < 3 了，這個時候就不必再加進佇列中了。因為比起已經合法的連續片段，那些長度還 ≧ 3 的片段明顯比較「緊急」。
如果上面的過程沒有把 D 次刪除之操作給消耗完也沒有關係，之後再隨便刪除若干個字元就好。只要避免把全部的大寫、小寫或是數字刪掉即可。而因為刪完之後長度會恰好是 20，因此根據鴿籠原理（Pigeonhole Principle）便可以保證我們可以避免這種情況發生。
假設處理完之後的非法（即長度 ≧ 3）的連續片段還需要 C 次替換操作。則我們可以仿照上面的作法——判斷 C 是否小於 (3 - (lower + upper + digit))。如果是，則最少所需步驟為 (3 - (lower + upper + digit)) + D（請不要忘記一開始 D 次的刪除之操作）；反之，則為 C + D 個步驟。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
