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)

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; } }