Strong Password Checker

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

  1. It has at least 6 characters and at most 20 characters.
  2. It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
  3. 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;
    }
}