420. 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:

1. Length problem:
   1. len < 6: insert
   2. len > 20: delete
2. Missing case: replace / insert
3. repeat: replace / delete / insert
4. First, solve len < 6 together with missing case problem with insert
5. Then solve the over length problem with repeat problem
   1. how to decide when to use replace or delete?
      1. to ensure the minimum change, not delete number repeat elements to <= 2, but to first reduce the number to the closest 3m + 2 value, where m will be the number of replace we need to do.
         1. for interger A % 3 == 0 ----> A -= 1 to get to 3m + 2, update the over_len -= 1
         2. for interger A % 3 == 1 -----> A -= 2 to get to 3m + 2, update the over_len -= 2
      2. After transforming all the repeat count number to 3m + 2 form, check if overlen > 0, then directly reduce the repeat count number to ( countnumber < 2 or overlen == 0)
      3. then do replace on the left repeat problem
6. Reference:
7. 1. https://discuss.leetcode.com/topic/63854/o-n-java-solution-by-analyzing-changes-allowed-to-fix-each-problem
   2. http://www.cnblogs.com/grandyang/p/5988792.html
   3. http://bookshadow.com/weblog/2016/10/21/leetcode-strong-password-checker/

public class Solution {
    public int strongPasswordChecker(String s) {
        int res = 0, a = 1, A = 1, d = 1;
        char[] carr = s.toCharArray();
        int[] arr = new int[carr.length];

        for (int i = 0; i < arr.length;) {
            if (Character.isLowerCase(carr[i])) a = 0;
            if (Character.isUpperCase(carr[i])) A = 0;
            if (Character.isDigit(carr[i])) d = 0;

            int j = i;
            while (i < carr.length && carr[i] == carr[j]) i++;
            arr[j] = i - j;
    }

    int total_missing = (a + A + d);

    if (arr.length < 6) {
        res += total_missing + Math.max(0, 6 - (arr.length + total_missing));

    } else {
        int over_len = Math.max(arr.length - 20, 0), left_over = 0;
        res += over_len;

        for (int k = 1; k < 3; k++) {
            for (int i = 0; i < arr.length && over_len > 0; i++) {
                if (arr[i] < 3 || arr[i] % 3 != (k - 1)) continue;
                arr[i] -= Math.min(over_len, k);
                over_len -= k;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= 3 && over_len > 0) {
                int need = arr[i] - 2;
                arr[i] -= over_len;
                over_len -= need;
            }

            if (arr[i] >= 3) left_over += arr[i] / 3;
        }

        res += Math.max(total_missing, left_over);
    }

    return res;

    }
}