题目描述

420. 强密码检验器

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

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

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

3

案例	输入	输出
1	a	5
2	aA1	3
3	1337C0d3	0

思路分析

• 这道题难就难在需要你给出优化步骤。不仅仅需要判定他是否符合强密码要求，还需要针对非强密码给出优化方案。
• 优化的方式题目中也给出说明了，我们一次操作仅可以新增，删除，修改一个字符。在针对密码长度我们会区分三种情况

• 那么我们下面也就是针对这三种情况进行针对性的操作

长度过小

• 题目中要求我们优化的方案仅有三种----新增，修改，删除1个字符一次。

• 当密码长度小于6的时候，我们如果想要优化成强密码格式。强密码要求之一是长度在6~20之内。那么我们删除的操作就没必要了。
• 那么我们再来看如果出现连续字符出现重复的情况，我们改怎么做。因为我们现在的密码长度是小于6的，所以最多出现连续5个字符相同，

相同字符5个

• 针对连续字符在5个情况中我们可以更新其中一个使其断开连续3个字符的效果。但是强密码还需要至少包含3中类型字符。在连续5个相同字符出现的情况下我们进行替换后元素种类才两种，所以我们还需要执行一次新增才可以满足强密码的要求

• 除了更新之后新增的方案以外，我们还可以直接在连续字符中已新增的方式来同事破解连续并且保证长度。

• 两种方案优化的步骤都是2

相同字符4个

• 因为当前大条件是密码长度不超过6 ， 相同字符4个。那么密码长度最大是5，也就是密码种类最多是2 。 那么此时针对相同字符是该替换还是新增就很明显了。
• 新增不仅可以破解连续的问题还可以解决种类新增的问题和长度的问题，而更新无法解决长度的问题，所以这里我们需要采用新增方式

• 所以我们选择在连续位置的中位数位置进行新增一个元素就完成了升级操作了。

相同字符3个

• 相同密码3个和4个是一样的。我们要做的是在中位数位置左右各新增就完成了。

公式

• 假设我们密码长度为n . 密码中出现字符的种类为t

• 为什么上面连续字符2,1,0个这三种情况就不在分析了。因为连续字符低于3我们就不需要关心了，直接新增就可以了。也就是说连续字符没有超过3时，我们优化的步骤6-n , 或者3-t 。这个就取决两者谁大了。 6-n是为了完成长度的满足，3-t 是为了完成种类的满足 。
• 相同字符3时，6-n
• 相同字符4时，6-n
• 相同字符5时，6-n

长度适中

• 长度适中意思就是长度在6~20之内，那么这个阶段很明显新增就不在适合我们的优化策略了，因为很有可能因为新增导致长度超出了。而且在破解连续字符的问题上我们是可以用更新或者删除来破解的。很明显在连续字符超过4的时候删除也不适合。所以综合来看在连续字符的问题上还是更新比较适合

• 不管连续多少个字符，我们只需要不出现连续三个字符出现就行。那么我们就只需要将连续的字符3个分组。每个组里我们替换掉1个就行了。假设我们连续字符分别为k1,k2,k3....kx
• 那么我们需要更新的操作是k/3之和

• 另外我们还需要记住保持三种类型，假设我们字符类型是t , 3-t就是我们需要的操作 ； 也就是我们去X 和3-t的最大值

长度过大

• 因为长度过大，所以这里新增很明显就不合适了，那么就是更新和删除。第一反应就是肯定删除合适。但是当我们删除到一定长度后还会出现连续字符这个情况，所以更新就必不可少了。
• 那么针对修复我们是先更新后删除，还是先删除后更新呢。

• 经过这么一张图，相信聪明的你应该也知道改选那种方式了吧。下面我们看下官网给出的解释，我觉得分析的和清晰

AC

​
class Solution {
    public int strongPasswordChecker(String password) {
        int n = password.length();
        int hasLower = 0, hasUpper = 0, hasDigit = 0;
        for (int i = 0; i < n; ++i) {
            char ch = password.charAt(i);
            if (Character.isLowerCase(ch)) {
                hasLower = 1;
            } else if (Character.isUpperCase(ch)) {
                hasUpper = 1;
            } else if (Character.isDigit(ch)) {
                hasDigit = 1;
            }
        }
        int categories = hasLower + hasUpper + hasDigit;
​
        if (n < 6) {
            return Math.max(6 - n, 3 - categories);
        } else if (n <= 20) {
            int replace = 0;
            int cnt = 0;
            char cur = '#';
​
            for (int i = 0; i < n; ++i) {
                char ch = password.charAt(i);
                if (ch == cur) {
                    ++cnt;
                } else {
                    replace += cnt / 3;
                    cnt = 1;
                    cur = ch;
                }
            }
            replace += cnt / 3;
            return Math.max(replace, 3 - categories);
        } else {
            // 替换次数和删除次数
            int replace = 0, remove = n - 20;
            // k mod 3 = 1 的组数，即删除 2 个字符可以减少 1 次替换操作
            int rm2 = 0;
            int cnt = 0;
            char cur = '#';
​
            for (int i = 0; i < n; ++i) {
                char ch = password.charAt(i);
                if (ch == cur) {
                    ++cnt;
                } else {
                    if (remove > 0 && cnt >= 3) {
                        if (cnt % 3 == 0) {
                            // 如果是 k % 3 = 0 的组，那么优先删除 1 个字符，减少 1 次替换操作
                            --remove;
                            --replace;
                        } else if (cnt % 3 == 1) {
                            // 如果是 k % 3 = 1 的组，那么存下来备用
                            ++rm2;
                        }
                        // k % 3 = 2 的组无需显式考虑
                    }
                    replace += cnt / 3;
                    cnt = 1;
                    cur = ch;
                }
            }
            if (remove > 0 && cnt >= 3) {
                if (cnt % 3 == 0) {
                    --remove;
                    --replace;
                } else if (cnt % 3 == 1) {
                    ++rm2;
                }
            }
            replace += cnt / 3;
​
            // 使用 k % 3 = 1 的组的数量，由剩余的替换次数、组数和剩余的删除次数共同决定
            int use2 = Math.min(Math.min(replace, rm2), remove / 2);
            replace -= use2;
            remove -= use2 * 2;
            // 由于每有一次替换次数就一定有 3 个连续相同的字符（k / 3 决定），因此这里可以直接计算出使用 k % 3 = 2 的组的数量
            int use3 = Math.min(replace, remove / 3);
            replace -= use3;
            remove -= use3 * 3;
            return (n - 20) + Math.max(replace, 3 - categories);
        }
    }
}
​

总结

• 这道题难就难在需要我们运用逻辑数学思维。分类讨论，每种情况做不同的策略就行了。具体代码按照思路实现即可

\