420. 强密码检验器 : 分情况讨论模拟题

题目描述

这是 LeetCode 上的 420. 强密码检验器 ，难度为 困难。

Tag : 「模拟」

如果一个密码满足下述所有条件，则认为这个密码是强密码：

• 由至少 66 个，至多 2020 个字符组成。
• 至少包含一个小写字母，一个大写字母，和一个数字。
• 同一字符不能连续出现三次 (比如 "...aaa..." 是不允许的, 但是 "...aa...a..." 如果满足其他条件也可以算是强密码)。

给你一个字符串 password，返回将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 00 。

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

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

示例 1：

输入：password = "a"
输出：5
复制代码

示例 2：

输入：password = "aA1"
输出：3
复制代码

示例 3：

输入：password = "1337C0d3"
输出：0
复制代码

提示：

• 1 <= password.length <= 501<=password.length<=50
• password 由字母、数字、点 '.' 或者感叹号 '!'

模拟（分情况讨论）

这是一道麻烦而又没啥意义的题。

需要满足的条件有三个，根据 password 的长度 nn，字符种类数量 mm，以及相同字符连续长度不低于 33 的情况 gg（数组 gg 的长度为相同字符长度不低于 33 的连续段个数，g[i]g[i] 代表第 ii 个连续段的长度），进行分情况讨论：

• n < 6n<6：长度过短，不满足要求，任何一次「删除」操作都需要额外搭配一个「增加」操作，而这两步操作可以使用「替换」来代替，结果不会变差；同时为了满足长度要求，我们必然要使用到「增加」操作。因此需要用到「增加」和「替换」操作，枚举所有的情况发现，最少操作次数最终可以归纳到 \max(6 - n, 3 - m)max(6−n,3−m)；
• 6 \leqslant n \leqslant 206⩽n⩽20：任何的有效的「增加」操作目的只能是为了「破坏连续段长度不低于 33」或者「增加字符种类数量」，这两个目的都可以使用「替换」来做到；而任何有效的「删除」操作只能是为了「破坏连续段长度不低于 33」，这一目的也可以使用「替换」来做到。因此只需要用到「替换」操作，结果不会变差。对于某个 g[i]g[i] 而言，我们需要使用 \left \lfloor \frac{g[i]}{3} \right \rfloor⌊3g[i]⌋ 次「替换」操作来满足「连续段长度不能不低于 33」的要求，在此基础上再考虑字符种类的问题，最少操作次数最终可以归纳到 \max(\sum_{i = 0}^{g.length - 1}\left \lfloor \frac{g[i]}{3} \right \rfloor, 3 - m)max(∑i=0g.length−1⌊3g[i]⌋,3−m)；
• n > 20n>20：长度过长，不满足要求，任何一次「增加」操作都需要额外搭配一个「删除」操作，只需要用到「删除」和「替换」操作，为了满足长度要求，必然用到的「删除」操作可能会影响到最终的「替换」操作，直觉上，应当优先删除那些「连续段长度不低于 33」的字符。由于连续段长度 g[i]g[i] 与其消耗的「替换」次数的关系为 \lfloor \frac{g[i]}{3} \rfloor⌊3g[i]⌋，在不考虑余数的情况下，每删除 33 个字符，能够连带的减少一次「替换」操作。因此我们可以根据 g[i]g[i] 对 33 取模进行统计，得到 cntscnts 数组（cntscnts 数组长度为 33，其中 cnts[i] = xcnts[i]=x 含义为在所有「连续段长度不低于 33」的连续段中，长度余数为 ii 的数量有 xx 个），按照余数从小到大的优先级进行同步抵消，得到最终的「替换」操作数 tottot（tottot 起始值为 \sum_{i = 0}^{g.length - 1}\left \lfloor \frac{g[i]}{3} \right \rfloor∑i=0g.length−1⌊3g[i]⌋）。除了可变的「替换」操作以外，我们不可避免还需要 base = n - 20base=n−20 的「删除」操作，最少操作次数可以归纳到 base + \max(tot, 3 - m)base+max(tot,3−m)

实现上，我们并不需要真正处理出来 gg 数组，可以边统计「连续段长度不低于 33」边累加需要的「替换」次数。

代码：

class Solution {
    public int strongPasswordChecker(String password) {
        char[] cs = password.toCharArray();
        int n = cs.length;
        int A = 0, B = 0, C = 0;
        for (char c : cs) {
            if (c >= 'a' && c <= 'z') A = 1;
            else if (c >= '0' && c <= '9') B = 1;
            else if (c >= 'A' && c <= 'Z') C = 1;
        }
        int m = A + B + C;
        if (n < 6) {
            return Math.max(6 - n, 3 - m);
        } else if (n <= 20) {
            int tot = 0;
            for (int i = 0; i < n; ) {
                int j = i;
                while (j < n && cs[j] == cs[i]) j++;
                int cnt = j - i;
                if (cnt >= 3) tot += cnt / 3;
                i = j;
            }
            return Math.max(tot, 3 - m);
        } else {
            int tot = 0;
            int[] cnts = new int[3];
            for (int i = 0; i < n; ) {
                int j = i;
                while (j < n && cs[j] == cs[i]) j++;
                int cnt = j - i;
                if (cnt >= 3) {
                    tot += cnt / 3; cnts[cnt % 3]++;
                }
                i = j;
            }
            int base = n - 20, cur = base;
            for (int i = 0; i < 3; i++) {
                if (i == 2) cnts[i] = tot;
                if (cnts[i] != 0 && cur > 0) {
                    int t = Math.min(cnts[i] * (i + 1), cur);
                    cur -= t; tot -= t / (i + 1);
                }
            }
            return base + Math.max(tot, 3 - m);
        }
    }
}
复制代码

• 时间复杂度：O(n)O(n)
• 空间复杂度：O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.420 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。