420. 强密码检验器

难点：当总长度超过20时，如何在删除的同时将长度大于等于3的连续子串一并消掉是个问题，如果有多个这样的子串，选哪些来消除？顺序如何？
考虑每个连续子串的长度，根据模3的余数进行分类
len % 3 == 0时，仅仅删除1个字符就能等效于一次修改操作
len % 3 == 1时，需要删除2个字符等效于一次修改操作
len % 3 == 2时，每次删除3个字符等效于一次修改操作
做法是在寻找连续子串的同时，记录其类别以及仅用修改操作需要的次数
之后根据要删除的字符数用等效替换的方式更新修改所需次数。

  1. class Solution {
  2.     public int strongPasswordChecker(String s) {
  3.         boolean a = false, b = false, c = false;
  4.         int n = s.length();
  6.         for (int i = 0; i < n; i++) {
  7.             char ch = s.charAt(i);
  8.             if (ch >= '0' && ch <= '9') a = true;
  9.             else if (ch >= 'a' && ch <= 'z') b = true;
  10.             else if (ch >= 'A' && ch <= 'Z') c = true;
  11.         }
  13.         int k = 0;
  14.         if (a) k++;
  15.         if (b) k++;
  16.         if (c) k++;
  18.         if (n < 6) return Math.max(6 - n, 3 - k);
  19.         else {
  20.             int p = 0, del = n - 20, res = del;
  21.             int[] d = new int[3];
  23.             for (int i = 0; i < n; i++) {
  24.                 int j = i;
  25.                 while (j < n && s.charAt(j) == s.charAt(i))
  26.                     j++;
  27.                 if (j - i >= 3) {
  28.                     d[(j - i) % 3]++;
  29.                     p += (j - i) / 3;
  30.                 }
  31.                 i = j - 1;
  32.             }
  33.             if (n <= 20) return Math.max(3 - k, p);
  34.             else {
  35.                 if (d[0] > 0 && del > 0) {
  36.                     int t = Math.min(d[0], del);
  37.                     p -= t;
  38.                     del -= t;
  39.                 }
  40.                 if (d[1] > 0 && del > 0) {
  41.                     int t = Math.min(d[1], del / 2);
  42.                     del -= t * 2;
  43.                     p -= t;
  44.                 }
  45.                 if (p > 0 && del > 0) {
  46.                     int t = Math.min(p, del / 3);
  47.                     del -= t * 3;
  48.                     p -= t;
  49.                 }
  50.                 return res + Math.max(p, 3 - k);
  51.             }
  52.         }
  53.     }
  54. }