LeetCode 420. 强密码检验器
目录
题目描述
题意分析
给一个字符串，问最少做多少次操作能让它同时满足三个条件：长度落在 $6$ 到 $20$ 之间（闭区间）、至少各含一个小写字母、大写字母和数字、不存在连续三个及以上相同的字符。可用的操作有三种，插入一个字符、删除一个字符、把某个字符替换成另一个，每种都记一次。
三个条件的性质完全不同，这是本题的难点来源。长度条件是个区间约束，太短要插、太长要删；字符种类条件只关心「有没有」，最多欠三笔；连续重复条件则和字符串的分段结构有关。三种操作对这三个条件的影响还互相交织——插入既能补长度也能打断重复段，替换既能补字符种类也能打断重复段，删除既能缩长度也能缩短重复段。
关键的信号在数据范围上：目标长度上限固定为 $20$，重复段的判定阈值固定为 $3$，欠缺的字符种类最多只有 $3$ 种。这些都是常数，意味着答案可以按长度落在哪个区间分三种情况分别推导，而不必写成统一的搜索。
边界方面：空串和长度为 $1$ 的串都要能正确返回；已经合法的串答案为 $0$；字符串里可能出现字母数字之外的符号（如
!），它们对种类条件没有贡献，但一样会构成重复段并占用长度。
解法：分类计数 + 贪心删除
核心思路
直接搜索所有操作序列显然不可行，操作空间是指数级的。换个思路：先分别算出每个条件单独需要多少次操作，再研究这些操作能否互相复用。
先做两项统计。第一项是
missing，即小写、大写、数字三类里缺了几类，取值范围是 $0$ 到 $3$，每缺一类至少要付出一次操作（插入或替换都行）。第二项是把字符串切成极大连续重复段，对每个长度为 $L \ge 3$ 的段，如果只允许替换，最少要改 $\lfloor L/3 \rfloor$ 次——每三个一组改中间那个，就能把这一段彻底打散；把所有段的 $\lfloor L/3 \rfloor$ 加起来记作replace。接下来按长度分情况。当 $n < 6$ 时必须插入 $6-n$ 个字符。这时插入操作威力极大：一次插入既能补长度，又能顺手插进重复段中间把它打断，还能选一个欠缺类型的字符补种类。由于 $n < 6$，任何重复段长度都不超过 $5$，最多只需一次插入就能打散，而需要的插入总数至少是 $6-n$，替换需求必然被完全覆盖，所以答案是 $\max(\text{missing},\ 6-n)$。
当 $6 \le n \le 20$ 时长度已经合法，不需要增删。此时替换操作同样可以身兼两职：打断重复段的那一次替换，完全可以顺便换成一个欠缺类型的字符。所以两项需求取较大者即可，答案是 $\max(\text{missing},\ \text{replace})$。
当 $n > 20$ 时必须删掉 $d = n - 20$ 个字符，这 $d$ 次删除是无论如何都省不掉的。真正的优化空间在于：删除的位置可以挑，删在重复段里能顺带降低
replace。这就变成一个分配问题——把 $d$ 次删除投到哪些段上，能让 $\lfloor L/3 \rfloor$ 的总和降得最多。对一段长度为 $L$ 的重复段，要把 $\lfloor L/3 \rfloor$ 降低 $1$，需要的删除次数取决于 $L \bmod 3$：余数为 $0$ 时只需删 $1$ 个（$L$ 降到 $L-1$，商减一）；余数为 $1$ 时需删 $2$ 个；余数为 $2$ 时需删 $3$ 个。而只要某段的长度先被调整成 $3$ 的倍数，之后每多删 $3$ 个就稳定再省一次替换。这就给出了贪心的排序依据：性价比从高到低是余数 $0$、余数 $1$、余数 $2$，先把删除额度喂给便宜的。因此只需统计三类段各有多少个（
mod0、mod1、mod2），按顺序消耗额度，最后把剩余额度按每 $3$ 个省 $1$ 次结算。答案是 $d + \max(\text{missing},\ \text{replace}')$，其中replace'是扣减后的替换需求。
解题步骤
- 扫一遍字符串，记录是否出现过小写字母、大写字母、数字，据此得出
missing。这一项和长度、重复段都无关，可以独立统计。- 再扫一遍，用双指针把字符串切成极大连续重复段。对每个长度 $L \ge 3$ 的段累加 $\lfloor L/3 \rfloor$ 到
replace，同时按 $L \bmod 3$ 把该段计入mod0、mod1或mod2三个计数器之一。长度小于 $3$ 的段不构成违规，直接跳过。- 若 $n < 6$，返回 $\max(\text{missing},\ 6-n)$。之所以不用管
replace，是因为此时每个重复段长度至多 $5$，一次插入即可打断，而插入次数至少为 $6-n \ge 1$，需求已被覆盖。- 若 $6 \le n \le 20$，返回 $\max(\text{missing},\ \text{replace})$。长度合法所以无需增删，替换与补种类可以共用同一次操作。
- 若 $n > 20$，令 $d = n - 20$ 并用
remaining追踪剩余删除额度。先用额度处理余数为 $0$ 的段，每段花 $1$ 次省 $1$ 次替换，可处理的段数是 $\min(\text{remaining},\ \text{mod0})$。之所以排在最前，是因为它的单位成本最低。- 接着处理余数为 $1$ 的段，每段花 $2$ 次省 $1$ 次，可处理段数是 $\min(\lfloor \text{remaining}/2 \rfloor,\ \text{mod1})$；再处理余数为 $2$ 的段，每段花 $3$ 次省 $1$ 次。这两步顺序不能颠倒，否则会把额度浪费在更贵的段上。
- 最后把剩下的额度按 $\lfloor \text{remaining}/3 \rfloor$ 折算成额外节省的替换次数——此时所有还有富余长度的段都已被调成 $3$ 的倍数形态，继续删每 $3$ 个必省 $1$ 次。返回 $d + \max(\text{missing},\ \text{replace}')$。
以
"aaaaBBBBBB11111dddddddd"走一遍：这个串由四段构成，aaaa长 $4$、BBBBBB长 $6$、11111长 $5$、dddddddd长 $8$，总长 $n = 23$。第一遍扫描发现小写（a、d）、大写（B）、数字（1）都出现过，所以 $\text{missing} = 0$。第二遍分段统计：aaaa贡献 $\lfloor 4/3 \rfloor = 1$ 且余数为 $1$；BBBBBB贡献 $\lfloor 6/3 \rfloor = 2$ 且余数为 $0$；11111贡献 $\lfloor 5/3 \rfloor = 1$ 且余数为 $2$；dddddddd贡献 $\lfloor 8/3 \rfloor = 2$ 且余数为 $2$。累计得 $\text{replace} = 1+2+1+2 = 6$，$\text{mod0} = 1$、$\text{mod1} = 1$、$\text{mod2} = 2$。因为 $n = 23 > 20$，删除额度 $d = 3$，remaining初值为 $3$。第一轮取 $\min(3, 1) = 1$，对BBBBBB删一个字符变成长 $5$，replace降为 $5$，remaining降为 $2$。第二轮取 $\min(\lfloor 2/2 \rfloor, 1) = 1$，对aaaa删两个字符变成长 $2$，replace降为 $4$，remaining降为 $0$。第三轮取 $\min(\lfloor 0/3 \rfloor, 2) = 0$，无操作。收尾时 $\lfloor 0/3 \rfloor = 0$，replace保持 $4$。最终答案是 $3 + \max(0, 4) = 7$。反向验算：删掉 $3$ 个字符后串形如aaBBBBB11111dddddddd，长度正好 $20$，四段分别需要 $0$、$1$、$1$、$2$ 次替换共 $4$ 次，加上 $3$ 次删除总计 $7$ 次，与算式吻合。
代码实现
// 统计所有连续重复段长度 len，其需要的替换次数为 len / 3。
class Solution {
public int strongPasswordChecker(String s) {
int n = s.length();
boolean hasLower = false;
boolean hasUpper = false;
boolean hasDigit = false;
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (Character.isLowerCase(ch)) {
hasLower = true;
} else if (Character.isUpperCase(ch)) {
hasUpper = true;
} else if (Character.isDigit(ch)) {
hasDigit = true;
}
}
int missing = 0;
if (!hasLower) {
missing++;
}
if (!hasUpper) {
missing++;
}
if (!hasDigit) {
missing++;
}
int replace = 0;
int mod0 = 0;
int mod1 = 0;
int mod2 = 0;
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) {
j++;
}
int len = j - i;
if (len >= 3) {
replace += len / 3;
int mod = len % 3;
if (mod == 0) {
mod0++;
} else if (mod == 1) {
mod1++;
} else {
mod2++;
}
}
i = j;
}
if (n < 6) {
return Math.max(missing, 6 - n);
}
if (n <= 20) {
return Math.max(missing, replace);
}
int delete = n - 20;
int remaining = delete;
int use = Math.min(remaining, mod0);
replace -= use;
remaining -= use;
use = Math.min(remaining / 2, mod1);
replace -= use;
remaining -= use * 2;
use = Math.min(remaining / 3, mod2);
replace -= use;
remaining -= use * 3;
replace -= remaining / 3;
return delete + Math.max(missing, replace);
}
}
// 统计所有连续重复段长度 len，其需要的替换次数为 len / 3。
func strongPasswordChecker(s string) int {
n := len(s)
hasLower := false
hasUpper := false
hasDigit := false
for i := 0; i < n; i++ {
ch := s[i]
if ch >= 'a' && ch <= 'z' {
hasLower = true
} else if ch >= 'A' && ch <= 'Z' {
hasUpper = true
} else if ch >= '0' && ch <= '9' {
hasDigit = true
}
}
missing := 0
if !hasLower {
missing++
}
if !hasUpper {
missing++
}
if !hasDigit {
missing++
}
replace := 0
mod0 := 0
mod1 := 0
mod2 := 0
for i := 0; i < n; {
j := i
for j < n && s[j] == s[i] {
j++
}
length := j - i
if length >= 3 {
replace += length / 3
switch length % 3 {
case 0:
mod0++
case 1:
mod1++
default:
mod2++
}
}
i = j
}
if n < 6 {
if missing > 6-n {
return missing
}
return 6 - n
}
if n <= 20 {
if missing > replace {
return missing
}
return replace
}
deleteCnt := n - 20
remaining := deleteCnt
use := remaining
if use > mod0 {
use = mod0
}
replace -= use
remaining -= use
use = remaining / 2
if use > mod1 {
use = mod1
}
replace -= use
remaining -= use * 2
use = remaining / 3
if use > mod2 {
use = mod2
}
replace -= use
remaining -= use * 3
replace -= remaining / 3
if missing > replace {
return deleteCnt + missing
}
return deleteCnt + replace
}
复杂度分析
- 时间复杂度：$O(n)$，$n$ 为字符串长度。第一遍扫描判断三类字符是否出现，第二遍用双指针切分重复段，两个指针都只单向前进，总移动量为 $n$。后续的贪心分配只在三个计数器上做常数次算术。
- 空间复杂度：$O(1)$。全程只用了三个布尔标志、
missing、replace以及mod0、mod1、mod2这几个整型变量，没有开任何与 $n$ 相关的数组或哈希表。
关键点总结
- 多个约束纠缠时，先把每个约束单独的代价算清楚，再问「同一次操作能不能同时满足两个约束」。本题的三段结论本质上都是在回答这个复用问题，答案分别是能完全复用（取 $\max$）和不能复用（相加）。
- 长度上下界这类区间约束会把问题天然切成互斥的几段，每段里可用的操作组合完全不同。识别出「$n<6$ 只插、$6 \le n \le 20$ 只换、$n>20$ 必删」是解题的第一个分水岭。
- 贪心的排序依据要能写成明确的「单位成本」。这里是「每省一次替换需要几次删除」，余数 $0$、$1$、$2$ 分别对应 $1$、$2$、$3$，成本清晰所以贪心正确性一目了然。
- 贪心结束后往往还剩下零头，需要一个统一的收尾公式。本题的 $\lfloor \text{remaining}/3 \rfloor$ 依赖于「所有段已被调成 $3$ 的倍数形态」这个前提，脱离前提就不成立。
- 面试视角：这题本身考的不是算法模板，而是分类讨论的完备性和推导的严密性。写代码前把三种长度区间、三种余数的成本表当着面试官口述一遍，比直接下笔更能拿分。
- 面试视角：面试官很可能追问「为什么 $n<6$ 时可以忽略
replace」和「为什么删除额度要按余数排序」。这两处是全题仅有的两个需要证明的点，准备好一句话解释即可。
易错点总结
- 错误写法：三种长度情况用
if / if / if而非互斥分支，或把 $n \le 20$ 的判断写在 $n < 6$ 之前 → 对"a"这样的输入会走进 $\max(\text{missing}, \text{replace}) = 2$ 的分支，而正确答案是 $5$。- 错误写法：$n > 20$ 时把答案写成 $\max(d,\ \text{missing},\ \text{replace}')$ → 删除和补种类是两类无法互相顶替的操作，对 $23$ 个相同小写字母的输入会少算 $d$ 次，结果偏小。
- 错误写法：$6 \le n \le 20$ 时把答案写成 $\text{missing} + \text{replace}$ → 对
"aaaaaa"会算出 $2 + 2 = 4$，但把其中两次替换分别换成大写字母和数字即可，正确答案是 $2$。- 错误写法：贪心时先处理余数为 $2$ 的段 → 对含一个余数 $0$ 段和一个余数 $2$ 段、额度为 $3$ 的输入，会花光 $3$ 次额度只省下 $1$ 次替换，而先处理余数 $0$ 的段能用 $1$ 次省 $1$ 次、剩余 $2$ 次仍有机会继续省，总代价被高估。
- 错误写法：余数为 $1$ 的段按每段消耗 $1$ 次额度计算 → 长度为 $4$ 的段删掉 $1$ 个仍是 $3$，$\lfloor 3/3 \rfloor$ 依然是 $1$，替换次数根本没降，
replace被错误地多减了。- 错误写法：统计重复段时把长度小于 $3$ 的段也计入
mod0、mod1、mod2→ 长度为 $1$ 的段余数为 $1$ 会混进mod1，贪心阶段以为花 $2$ 次删除能省一次替换，实际这段本来就不需要替换，replace被减成负数。- 错误写法：判断字符种类时用
else if链且把数字判断放在字母判断能覆盖的分支后仍漏掉非字母数字字符的处理 → 对含!等符号的输入若误把它计入某一类，missing偏小，答案偏小。- 错误写法：收尾时忘记 $\lfloor \text{remaining}/3 \rfloor$ 这一步 → 对只有一个超长重复段、删除额度远大于该段余数所需的输入（例如 $50$ 个相同字符），剩余的大量删除额度白白浪费，答案偏大。
- 错误写法：$n < 6$ 时直接返回 $6 - n$ 而不与
missing取较大值 → 对"aaaaa"会返回 $1$，但这个串还缺大写字母和数字两类，只插一个字符补不齐，正确答案是 $\max(2, 1) = 2$。- 错误写法：分段时内层循环用
s.charAt(j) == s.charAt(j-1)且不保护j的下界 → 段起点处会访问越界或误与上一段末字符比较，导致段边界整体错位一位，所有统计连锁出错。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 65. 有效数字 | 困难 | 同样是多条互相纠缠的格式规则，但只需判定合法性无需最小代价 |
| 468. 验证IP地址 | 中等 | 分类讨论的完备性训练，重点在切分与逐段校验的边界 |
| 443. 压缩字符串 | 中等 | 同样用双指针切极大重复段，但要求原地写回结果 |
| 38. 外观数列 | 中等 | 重复段统计的迭代应用，考察段长与字符的正确拼接 |
| 424. 替换后的最长重复字符 | 中等 | 替换次数受限下求最长同字符窗口，用滑动窗口而非分段贪心 |