LC 420. 强密码检验器

题目描述

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

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

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

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

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

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

示例 1：

1
2
3
输入：password = "a"

输出：5

示例 2：
1
2
3
输入：password = "aA1"

输出：3

示例 3：
1
2
3
输入：password = "1337C0d3"

输出：0

提示：

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

模拟（分情况讨论）

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

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

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

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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(1)$

最后

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

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

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

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