[LeetCode] Strong Password Checker 密碼強度檢查器

A password is considered strong if below conditions are all met:

It has at least 6 characters and at most 20 characters.

It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.

It must NOT contain three repeating characters in a row ("...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).

Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUM change required to make s a strong password. If s is already strong, return 0.

Insertion, deletion or replace of any one character are all considered as one change.

1. 長度問題，當長度小于6的時候，我們要通過插入字元來補充長度，當長度超過20時，我們要删除字元。

2. 缺失字元或數字，當我們缺少大寫，小寫和數字的時候，我們可以通過插入字元或者替換字元的方式來補全。

3. 重複字元，這個也是本題最大的難點，因為插入，删除，或者置換都可以解決重複字元的問題，比如有一個字元串"aaaaa"，我們可以用一次置換，比如換掉中間的字元'a'；或者兩次插入字元，在第二個a和第四個a後面分别插入一個非a字元；或者可以删除3個a來解決重複字元的問題。由于題目要求我們要用最少的步驟，那麼顯而易見置換是最高效的去重複字元的方法。

我們通過舉例觀察可以知道這三種情況并不是互相獨立的，一個操作有時候可以解決多個問題，比如字元串"aaa1a"，我們在第二個a後面增加一個'B'，變為"aaBa1a",這樣同時解決了三個問題，即增加了長度，又補充了缺失的大寫字母，又去掉了重複，是以我們的目标就是盡可能的找出這種能解決多種問題的操作。由于情況三(重複字元)可以用三種操作來解決，是以我們分别來看能同時解決情況一和情況三，跟同時解決情況二和情況三的操作。對于同時解決情況一和情況二的操作如果原密碼串長度小于6會有重疊出現，是以我們要分情況讨論：

當密碼串長度小于6時，情況一和情況二的操作步驟可以完全覆寫情況三，這個不難了解，因為這種情況下重複字元個數的範圍為[3,5]，如果有三個重複字元，那麼增加三個字元的操作可以同時解決重複字元問題("aaa" -> "a1BCaa"；如果有四個重複字元，那麼增加二個字元的操作也可以解決重複問題("aaaa" -> "aa1Baa")；如果有五個重複字元，那麼增加和置換操作也同時解決重複問題("aaaaa" -> "aa1aaB")。是以我們就專心看最少多少步能同時解決情況一和情況二，首先我們計算出目前密碼串需要補幾個字元才能到6，補充字元的方法隻能用插入字元操作，而插入字元操作也可以解決情況二，是以當情況二的缺失種類個數小于等于diff時，我們不用再增加操作，當diff不能完全覆寫缺失種類個數時，我們還應加上二者的內插補點。

當密碼串長度大于等于6個的時候，這種情況就比較複雜了，由于目前字元串的長度隻可能超标不可能不達标，是以我們盡量不要用插入字元操作，因為這有可能會使長度超過限制。由于長度的不确定性，是以可能會有大量的重複字元，那麼解決情況三就變得很重要了，由于前面的分析，替換字元是最高效的解法，但是這種方法沒法解決情況一，因為長度超标了的話，再怎麼替換字元，也不會讓長度減少，但是我們也不能無腦删除字元，這樣不一定能保證是最少步驟，是以在解決情況三的時候還要綜合考慮到情況一，這裡用到了一個trick (很膜拜大神能想的出來)，對于重複字元個數k大于等于3的情況，我們并不是直接将其删除到2個，而是先将其删除到最近的(3m+2)個，那麼如果k正好被3整除，那麼我們直接變為k-1，如果k除以3餘1，那麼變為k-2。這樣做的好處是3m+2個重複字元可以最高效的用替換m個字元來去除重複。那麼下面我們來看具體的步驟，首先我們算出超過20個的個數over，我們先把over加到結果res中，因為無論如何這over個删除操作都是要做的。如果沒超過，over就是0，用變量left表示解決重複字元最少需要替換的個數，初始化為0。然後我們周遊之前統計字元出現個數的數組，如果某個字元出現個數大于等于3，且此時over大于0，那麼我們将個數減為最近的3m+2個，over也對應的減少，注意，一旦over小于等于0，不要再進行删除操作。如果所有重複個數都減為3m+2了，但是over仍大于0，那麼我們還要進一步的進行删除操作，這回每次直接删除3m個，直到over小于等于0為止，剩下的如果還有重複個數大于3的字元，我們算出置換字元需要的個數直接加到left中即可，最後我們比較left和missing，取其中較大值加入結果res中即可，參見代碼如下：