Strong Password CheckerStrong 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.

The problem can be split to three parts(quite obvious) :

1. if the password contains all three types;
2. If the password has at least 6 chars and at most 20 chars;
3. If the password doesn't have any three or more repeating characters.

Now for the first part, we can go through the string and use a flag, whenever we see a type, we mark that type to true. In the end, we can get how many types we have in the password, and also how many types we still need. And the second part is fairly easy, check the length of the string.

The third part is the hardest. We know for every 3 - 5 repeating characters, we only need to modify one character to cut down the repeating length. similarly for every 6 - 8 repeating characters, we need to modify 2 characters, thus the number of characters needs to be modified = number of repeating characters / 3. After we go through the string, we will know how many changes we need to make.

If the length of the string exceeds 20, we know deletion is necessary. So we need to find out how many changes that can be modified by deletion. For each extra repeating word we have, we need to delete it. For example, if we have 5 repeating characters, we need delete 2, and if we have 4, we need to delete 1. We know that if we have 4 or 5 repeating characters, we only need to modify 1 character. So each modification operation can be replaced by number of repeating characters % 3 + 1 deletions. For example, 5 % 3 = 2, we need 2 + 1 = 3 deletion operations, but we only need 1 change operation. So when we go through the string, we also track how many deletion operations we can have instead of change operations. In the end if the length is greater than 20, we reduce the change operations by deletion operation.

If the length of the string is less than 6, adding a character is similar to replace a character, so the change required = max( 6 - len, # type required, # changes).

public int strongPasswordChecker(String s) {
        int len = s.length();
        
        if(len <= 2)  {
            return 6 - len;
        }
            

        char end = s.charAt(0);
        boolean upper = (end >= 'A' && end <= 'Z'), lower = (end >= 'a' && end <= 'z'), digit = (end >= '0' && end <= '9');
        
        
        //delete[0] indicates 1 change operation can be replaced by 1 deletion
        //delete[1] indicates 1 change operation can be replaced by 2 deletion
        int[] delete = new int[3];
        int change = 0;
        
        int repeating = 1;
        for(int i = 1; i < len; i++){
            if(s.charAt(i) == end) {
                repeating++;
            }
            else{
                change += (repeating / 3);
                if(repeating / 3 > 0) {
                    delete[repeating % 3] += (repeating / 3);
                }
                end = s.charAt(i);
                upper |= (end >= 'A'&& end<='Z');
                lower |= (end >='a' && end<='z');
                digit |= (end >= '0'&& end<='9');
                repeating = 1;
            }
        }
        //if last char equals to the char before, need to count repeating chars for the last one
        if (s.charAt(len - 1) == end) {
            change += repeating / 3;
            if(repeating / 3 > 0) delete[repeating % 3] += (repeating / 3);

        }        
        
        int typeStillNeeded = (upper ? 0 : 1) + (lower ? 0 : 1) + (digit ? 0 : 1);
        
        if(len > 20){
            int delRequired = len - 20;
            //since deletion requires more operations at most of the time, delete only when necessary
            if(delRequired <= delete[0]) {
                change -= delRequired;
            }
            // delete[1] indicates #repeating % 3 == 1, thus one change requires two deletions
            else if(delRequired - delete[0] <= 2 * delete[1]) {
                change -= delete[0] + (delRequired - delete[0]) / 2;
            }
            else {
                change -= delete[0] + delete[1] / 2 + (delRequired - delete[0] - 2 * delete[1]) / 3;
            }
            
            return delRequired + Math.max(typeStillNeeded, change);
        }
        return Math.max(6 - len, Math.max(typeStillNeeded, change));
    }