LeetCode 420. 强密码检验器
题目描述
题意分析
每次可以插入、删除或替换一个字符，求最少操作次数，使密码长度在 6 到 20 之间，至少包含一个小写字母、一个大写字母和一个数字，并且没有连续三个相同字符。这三个要求可能由同一次修改同时满足，不能分别算完后直接相加。
解法：分类计数 + 贪心删除
核心思路
[!blue]
先统计两种缺口：
missing是大小写字母、数字这三类中缺少的类别数；replace是不改变长度时，消除连续重复所需的最少替换次数。对一个长度为len的连续相同字符段，每隔三个字符替换一个，就能打散全部三连，因此贡献为len / 3。不同重复段互不影响，把这些贡献相加即可。长度在 6 到 20 之间时，不需要插入或删除。每次替换只能补入一种缺失类别，也至多消除一个上述替换缺口，所以至少需要
max(missing, replace)次。把用于打散重复的替换字符优先选成缺少的类别，就能同时完成两项要求；若类别仍不足，再做额外替换，因此这个下界可以达到。长度小于 6 时，至少要补
6 - n个字符，也至少要补齐missing个类别，答案为max(missing, 6 - n)。这些插入可以同时用于分隔重复段。此时最多只有一个长度至少为 3 的重复段：长度为 3 或 4 时，一次插入就能打散；长度为 5 时虽然需要两次，但整个串只含一种字符，至少缺两类，公式本来就会给出至少两次操作。因此无需再把replace单独加上。长度大于 20 时，至少必须删除
delete = n - 20个字符。删除不能补入缺失类别，却可能减少后续替换，应尽量把这些必需的删除用在重复段上。对长度为len的段，比较删除前后的len / 3：
len % 3 == 0：先删 1 个就能少替换一次。len % 3 == 1：先删 2 个才能少替换一次。len % 3 == 2：先删 3 个才能少替换一次。上面每次节省的都是一次替换，所以先选需要 1 次删除的段，再选需要 2 次删除的段。完成这种首次削减后，段长的余数都变成 2，之后每再删 3 个才继续节省一次替换；原先余数为 2 的段也按这个成本处理。若先把删除额度花在更贵的节省上，改为较便宜的节省只会留下更多额度，因此这种顺序最优。
代码用
mod0、mod1、mod2统计三类重复段的个数，逐批分配删除额度，无需保存每个段。删除时可以保留已有字符类别，再让剩余替换同时补类别和打散重复，最终答案为delete + max(missing, 剩余替换数)。超过必需数量的额外删除至少花一步，至多再省一步替换，不会让总操作更少。
解题步骤
- 扫描字符，计算
missing；按连续相同字符分组，累计replace和各余数类别的段数。n < 6时返回max(missing, 6 - n)；n <= 20时返回max(missing, replace)。- 长串先确定必须删除的总数，再从余 0 段各删 1 个，从余 1 段各删 2 个，每完成一份就将
replace减一。- 剩余额度按每 3 次删除减少一次替换，最后加上仍需完成的类别与重复修复次数。
最后一批删除直接用整数除法扣减，可能使计算变量
replace小于 0，这不表示真实替换次数为负。实际需求至少为 0；代码最终与非负的missing取最大值，已经包含了这个下限。
代码实现
// 统计所有连续重复段长度 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)$，分类与重复段扫描后仅常数次分配计算。
- 空间复杂度：$O(1)$，只保存类别与重复段统计。
关键点总结
[!green]
- 插入或替换可以同时补齐类别并打散重复，因此重叠的需求取最大值。
- 长串必须付出缩短长度的删除成本，再计算剩余修复，二者需要相加。
- 删除对替换数的收益由重复段长度模 3 决定，先完成成本最低的收益。
- 分类计数已经足够，不需要真正构造修改后的密码。
易错点总结
[!yellow]
- 五连相同字符只插一次仍会留下三连，必须同时考虑缺失类别。
- 长串只取删除与替换的最大值，漏掉必须独立付出的删除。
- 优先花三次删除处理余二段，可能错失一加二删除分别省两次替换。
mod0、mod1、mod2只统计长度至少为 3 的重复段，短段没有可节省的替换。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2299. 强密码检验器 II | 简单 | 原题只检查密码是否满足规则，本题要计算最少增删改次数，规则细节及长度限制也不同。 |