420. 强密码检验器

题目

如果一个密码满足下述所有条件，则认为这个密码是强密码：
由至少 6 个，至多 20 个字符组成。
至少包含 一个小写 字母，一个大写 字母，和 一个数字 。
同一字符 不能 连续出现三次 (比如 “…aaa…” 是不允许的, 但是 “…aa…a…” 如果满足其他条件也可以算是强密码)。
给你一个字符串 password ，返回 将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 0 。

在一步修改操作中，你可以：

插入一个字符到 password ，
从 password 中删除一个字符，或
用另一个字符来替换 password 中的某个字符。

示例 1：

输入：password = “a”
输出：5

示例 2：

输入：password = “aA1”
输出：3

示例 3：

输入：password = “1337C0d3”
输出：0

提示：

1 <= password.length <= 50
password 由字母、数字、点 ‘.’ 或者感叹号 ‘!’

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/strong-password-checker
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

近期做的最磨人的一道题…

题意很好理解，大致的思路也比较容易想，按照强密码的要求先把需要统计的变量统计出来，比如小写字母个数，大写字母个数，数字个数，这三者都必须满足最少为，缺失的使用保存，表示需要插入的字符数。

还需要记录长度不小于的连续相等的子串长度，例如对于输入”bbaaaaaaaaaaaaaaaacccccc”，和有连续长度不小于的子串，长度分别为和，因为连续相同的长度不能超过，因此每三个相同的字符就需要替换掉一个，先基于此生成一个变量表示需要替换的字符数，对于是，对于是。

然后，长度要满足到，如果满足长度要求且和都为（分别表示大小写字母数字都不缺以及没有连续不小于的子串），那么就返回。

如果不满足要求就按长度分情况讨论，因为不同的长度需要的操作不同：

• 长度不足的话，我们不需要替换操作，因为即使有连续不小于的子串，我们还要补全不够的那几个长度，穿插在连续的字符中间就好了，所以，操作最大次数为#card=math&code=max%286-n%2C%20inc%29&id=CeES9)，表示和最小长度的差距。
• 长度如果介于，即长度满足要求，别的不满足，这种情况我们无需进行删除操作，只需要替换或者插入，因为纯粹的删除操作是无意义的，长度已经满足同条件了，不需要删除，这种情况最大操作次数为#card=math&code=max%28rep%2C%20inc%29&id=eFZQB)
• 相比于前两种情况，长度大于是最难考虑的，这种情况，我们无需进行插入操作，同样因为纯粹的插入操作没有意义，如果缺什么字符替换别的就好了，长度肯定可以保证。首先，多出来的长度肯定需要删除，个操作步数省略不了，然后就是替换，如果存在连续不小于的子串，我们贪心地将其替换，如果还存在缺失必需的个字符，优先使用这几个字符去替换。在连续的需要替换的子串中，我们需要首先替换长度对取余后尽可能小的那一个字符，例如对于“bbaaaaaaaaccccccdddddd”，长度为，需要最少删除个，有个，和有个，我们优先删除和，因为和个数对取余后更小，各自删除一个后，和的替换次数就可以各自减，而要减去的一个删除次数需要删除个。因此，我们统计连续不小于的子串长度对取余的情况，使用记录，数组长度为，表示长度对取余的子串个数，对前面的例子，两个取余为，一个取余为。优先删除连续长度对3取余更小的字符可以尽可能减小，使得操作次数更小。

大致思路就是这样，文字描述难免会讲不清楚，记录一下，下面简单在代码中注释一下，不枉做了半天…

代码

class Solution {
    public int strongPasswordChecker(String password) {
        int n = password.length();
        int up = 0;
        int low = 0;
        int num = 0;
        for (int i = 0; i < n; i++) {
            char c = password.charAt(i);
            if (c >= 'a' && c <= 'z') {
                low++;
            } else if (c >= 'A' && c <= 'Z') {
                up++;
            } else if (c >= '0' && c <= '9') {
                num++;
            }
        }
        // 因为连续长度不小于3，需要替换的字符个数
        int rep = 0;
        int[] mod = new int[3];
        for (int i = 0; i < n; i++) {
            int k = i + 1;
            char c = password.charAt(i);
            while (k < n && password.charAt(k) == c) {
                k++;
            }
            // mod只统计连续相同长度不小于3的，因此加了这个if判断
            if (k - i >= 3) {
                rep += (k - i) / 3;
                mod[(k - i) % 3]++;
            }
            i = k - 1;
        }
        // 不满足至少一个大小写字母或者数字，需要增加的字符个数
        int inc = 0;
        if (up == 0) {
            inc++;
        }
        if (low == 0) {
            inc++;
        }
        if (num == 0) {
            inc++;
        }
        // 满足要求，返回0
        if (n >= 6 && n <= 20 && inc == 0 && rep == 0) {
            return 0;
        }
        int ans = 0;
        if (n < 6) {
            ans += Math.max(6 - n, inc);
        } else if (n <= 20) {
            ans += Math.max(rep, inc);
        } else {
            // k为超出的，至少要删除的字符个数
            int k = n - 20;
            // 遍历mod数组的下标，从0开始对应从余数为0的开始删除
            int j = 0;
            // 删除k个字符，尽可能优先删除连续长度对3取余更小的字符
            // mod如果都为0表示没有连续的需要替换的字符，不进入循环
            while ((mod[0] > 0 || mod[1] > 0 || mod[2] > 0) && k > 0) {
                // 对于余数为 j % 3 的字符，需要删除 j % 3 + 1个，即余数为0删除1个、余数为1删除2个、余数为2删除3个
                // cnt表示删除了cnt种余数为 j % 3 的字符，每种字符删除了 j % 3 + 1 个
                int cnt = Math.min(mod[j % 3] * (j % 3 + 1), k) / (j % 3 + 1);
                // k减掉删除的字符个数
                k -= mod[j % 3] * (j % 3 + 1);
                // 删除后，余数都变为2了，余数为 2 的多了cnt个
                mod[2] += cnt;
                // 余数为 j % 3 的少了cnt个
                mod[j % 3] -= cnt;
                // 需要替换的次数也减小了cnt
                rep -= cnt;
                j++;
            }
            ans += n - 20 + Math.max(inc, rep);
        }
        return ans;
    }
}