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.
Solution:
Time: O(n) Space: O(n)
class Solution {
public int strongPasswordChecker(String s) {
int result = 0, n = s.length(), lower = 1, upper = 1, digit = 1;
int[] repeat = new int[n];
for (int i = 0; i < n; ) {
char c = s.charAt(i);
if (c >= 'a' && c <= 'z') lower = 0;
if (c >= 'A' && c <= 'Z') upper = 0;
if (c >= '0' && c <= '9') digit = 0;
int start = i;
while (i < n && s.charAt(i) == s.charAt(start)) i ++;
repeat[start] = i - start; // number of repetition
}
int missType = lower + upper + digit;
/*
if n is smaller than 6, we have to insert the diff (6-n)
if diff is smaller than 3 (the # of letter types), we need to insert missType
e.g. aaaaa, we must add uppercase and digit anyway, even if diff=1
*/
if (n < 6) {
result = Math.max(missType, 6 - n);
} else {
// if number is greater than 20
int over = Math.max(n - 20, 0);
int replace = 0;
// we will need to remove `over` characters anyway
result += over;
/*
We know that for (3m+2) letters, we only need to replace m letters
Remove 1 or 2 letters to convert repeat[start] in the form of 3m+2
where m is an integer.
e.g.
aaaaaaaaabbbbbbbb (9 a's and 8 b's), remove 1 a to make 8 = 3m+2, where m = 2
*/
for (int i = 0; i < n && over > 0; i ++) {
if (repeat[i] < 3) continue;
if (repeat[i] % 3 == 0) { //e.g. 9 a's, need to remove 1
repeat[i] -= 1;
over -= 1; //already removed one;
}
}
for (int i = 0; i < n && over > 0; i ++) {
if (repeat[i] < 3) continue;
if (repeat[i] % 3 == 1) { //e.g. 7 a's, need to remove 2 to become 3*1+2=5
repeat[i] -= Math.min(2, over);
over -= 2;
}
}
//over is the remaining letters that need to be removed
//if removal can fix the repetition issue, we don't need to replace
for (int i = 0; i < n; i++) {
if (repeat[i] >= 3 && over > 0) {
int needToRemove = repeat[i] - 2; // can have 2 repeating elements
repeat[i] -= Math.min(needToRemove, over);
over -= needToRemove;
}
if (repeat[i] >= 3) replace += repeat[i]/3; //at least replace m
}
//System.out.println(missType + " " + replace);
result += Math.max(missType, replace);
}
return result;
}
}