# LintCode领扣 题解丨阿里高频面试题：密码强度检查器

【题解】

public class Solution {

/**
* @param s: a string
* @return: return an integer
*/
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;

}

+ 订阅