當以下條件都滿足時，一個密碼被視為是強密碼：
至少包含6個字符，但不超過20個字符。
至少包含一個小寫字母，一個大寫字母，和一個數字。
不能包含三個連續的重複字符（"...aaa..."是弱密碼，但"...aa...a..."是強密碼，假設它們的其他條件都滿足了）。
寫一個函數strongPasswordChecker(s)，它將一個字符串s作為輸入，並且返回將其轉換成強密碼需要的最少改變次數。如果s已經是一個強密碼了，返回0。
插入、刪除或者替換任意一個字符都視為一次改變。
在線評測地址：https://www.lintcode.com/problem/strong-password-checker/?utm_source=sc-tc-sz0811
樣例 1:
輸入："aaa123"
輸出：1
解釋："aaa123"->"aaA123"
樣例 2:
輸入："a"
輸出：5
解釋："a"->"aa"->"aaA"->"aaA1"->"aaA12"->"aaA123"
【題解】
考點：
思維
題解：本題根據要求最小的改變次數，確定修改策略即可。
變為強密碼需要解決三種問題：
長度小於6時需要插入字符，長度大於20時需要刪除字符
缺失字符或數字，此時可以通過插入或者替換字符解決
出現三個及以上重複字符，利用置換解決該問題會更好，可以同時做到解決情況二和情況三。
接下來，按照長度進行討論。
當長度小於6時，儘量採用插入操作，既可以增加長度也可以避免重複字符連續。
當長度大於等於6時，對於重複字符個數k大於等於3的情況，先將其刪除到最近的(3m+2)個，那麼如果k正好被3整除，那麼我們直接變為k-1，如果k%3=1，那麼變為k-2。這樣做的好處是3m+2個重複字符可以用替換m個字符來去除重複，然後遍歷一次，進行刪除和替換，可以直接刪除3m個，最少刪除操作。
public class Solution {
/**
* @param s: a string
* @return: return an integer
*/
public int strongPasswordChecker(String s) {
// write your code here
int res = 0, n = s.length(), lower = 1, upper = 1, digit = 1;
int [] v = new int [n];
for (int i = 0; i < n;) { //遍歷是否存在缺失字符種類
if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
lower = 0;
}
if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
upper = 0;
}
if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
digit = 0;
}
int j = i;
while (i < n && s.charAt(i) == s.charAt(j)) {
++i;
}
v[j] = i - j; //標記j位置開始連續重複字符的數量
}
int missing = (lower + upper + digit); //缺失的字符種類數
if (n < 6) {
int diff = 6 - n; //缺失的長度
res += diff + Math.max(0, missing - diff); //缺失長度加上missing - diff差值(因為增加的字符不一定補全字符種類，替換)
}
else {
int over = Math.max(n - 20, 0), left = 0; //超出長度
res += over;
for (int k = 1; k < 3; ++k) { //如果重複數量k%3==0，-1達到3m+2。如果k%3==1，-2達到3m+2
for (int i = 0; i < n && over > 0; ++i) {
if (v[i] < 3 || v[i] % 3 != (k - 1)) {
continue;
}
v[i] -= k;
over -=k; //刪除字符
}
}
for (int i = 0; i < n; ++i) {
if (v[i] >= 3 && over > 0) {
int need = v[i] - 2; //通過-2得到3m
v[i] -= over;
over -= need; //直接選擇刪除3m個
}
if (v[i] >= 3) { //如果v[i]>=3那麼需要進行替換操作
left += v[i] / 3;
}
}
res += Math.max(missing, left); //每次除以3即為替換的字符個數
}
return res;
}}
更多題解參見九章算法官網：
https://www.jiuzhang.com/solution/strong-password-checker/?utm_source=sc-tc-sz0811