LeetCode [420] Strong Password Checker

 420. Strong Password Checker

Hard

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

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; } //missing lowerCase + upperCase + digit int total_missing = (a + A + d); if (arr.length < 6) { //at most 1 segment with >=3 repeating chars, which can be resolve whiling filling total_missing char 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; //while removing over_len, we can fix 3-repeating segments //deal with xxx and xxxx by remove 1 and 2 from them 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; } //left 3-repeated segments //xxxxxxxyyy -> xx1xx1xyyZ if (arr[i] >= 3) left_over += arr[i] / 3; } res += Math.max(total_missing, left_over); } return res; } }