1
class Solution {
2
  private static final int MIN_LENGTH = 6;
3
  private static final int MAX_LENGTH = 20;
4

5
  public int strongPasswordChecker(String password) {
6
    int numMissingComponents = getNumberOfMissingComponents(password);
7
    int n = password.length();
8

9
    if (n < MIN_LENGTH) {
10
      return Math.max(numMissingComponents, MIN_LENGTH - n);
11
    }
12

13
    List<Integer> repeats = buildRepeatList(password);
14

15
    int over = Math.max(0, n - MAX_LENGTH);
16
    int numRemoval = over;
17

18
    // use overage for repeat % 3 == 0 case. One removal would reduce one replacement
19
    for (int i = 0; i < repeats.size() && over > 0; i++) {
20
      int repeat = repeats.get(i);
21
      if (repeat >= 3 && repeat % 3 == 0) {
22
        repeats.set(i, repeat - 1);
23
        over--;
24
      }
25
    }
26
    // use overage for repeat % 3 == 1 case. Two removal would reduce one replacement
27
    for (int i = 0; i < repeats.size() && over > 0; i++) {
28
      int repeat = repeats.get(i);
29
      if (repeat >= 3 && repeat % 3 == 1) {
30
        repeats.set(i, repeat - Math.min(over, 2));
31
        over -= Math.min(over, 2);
32
      }
33
    }
34

35
    int numReplace = 0;
36
    for (int repeat : repeats) {
37
      if (over > 0 && repeat >= 3) {
38
        int reduce = Math.min(over, repeat - 2);
39
        over -= reduce;
40
        repeat -= reduce;
41
      }
42
      if (repeat >= 3) {
43
        numReplace += repeat / 3;
44
      }
45
    }
46

47
    return Math.max(numReplace, numMissingComponents) + numRemoval;
48
  }
49

50
  private List<Integer> buildRepeatList(String password) {
51
    List<Integer> repeats = new ArrayList<>();
52
    for (int i = 0; i < password.length(); i++) {
53
      if (i == 0 || password.charAt(i) != password.charAt(i - 1)) {
54
        repeats.add(1);
55
      } else {
56
        int last = repeats.size() - 1;
57
        repeats.set(last, repeats.get(last) + 1);
58
      }
59
    }
60
    return repeats;
61
  }
62

63
  private int getNumberOfMissingComponents(String password) {
64
    int digit = 1;
65
    int upper = 1;
66
    int lower = 1;
67
    for (char c : password.toCharArray()) {
68
      if (Character.isDigit(c)) {
69
        digit = 0;
70
      }
71
      if (Character.isLowerCase(c)) {
72
        lower = 0;
73
      }
74
      if (Character.isUpperCase(c)) {
75
        upper = 0;
76
      }
77
    }
78
    return digit + upper + lower;
79
  }
80
}