0420. Strong Password Checker¶
题目信息¶
- 题号:
0420
- 难度:
Hard
- 主题:
密码规则、插入删除替换、字符类别、连续重复
- 原题:
- 重点:
长度必须为 6 至 20、同时包含小写/大写/数字、不能有三个连续相同字符、返回最少编辑次数
题目重述¶
给定字符串 password,每次操作可以插入一个字符、删除一个字符或把一个字符替换为另一个字符。返回把它变成强密码所需的最少操作次数。
强密码必须同时满足:长度位于 [6, 20];至少包含一个小写英文字母、一个大写英文字母和一个数字;不能出现三个或更多连续相同字符。输入长度位于 [1, 50],字符只可能是字母、数字、句点 . 或感叹号 !。一次编辑可以同时改善多个规则缺陷,但仍只计作一次操作。
自建示例¶
只缺少长度:
输入:password = "Aa1b"
输出:2
解释:三种字符类别已经齐全且没有三连字符,但长度只有 4;插入两个适当字符即可达到长度 6,因此最少需要 2 次操作。
字符类别齐全但存在长重复段:
输入:password = "aaaaaA1"
输出:1
解释:长度和字符类别均合格,只需把五个连续 a 中的一个替换成其他字符,即可打断所有三个连续相同字符的情况。
先分离长度、类别和重复段三种缺陷¶
统计是否缺少小写、大写、数字三类字符,并把每段连续相同字符长度为 len 的替换需求记为 len / 3。当长度小于 6 时,插入操作既能补长度,也可能顺便补类别或打断重复,最优次数是 max(6-n, missing);长度在 6 到 20 之间时,只需在缺少类别和重复段替换之间取较大值。
长度超过 20 时必须先删除 n-20 个字符。删除应优先作用于 len % 3 == 0 的重复段:删 1 个就能减少 1 次替换;其次处理余数为 1 的段,删 2 个减少 1 次;剩余删除每 3 个再减少 1 次替换。删除完成后,剩余替换次数与缺少类别数可以由同一批替换操作共同承担,因此还要取二者最大值。
C++ 实现¶
class Solution {
public:
int strongPasswordChecker(std::string password) {
int n = static_cast<int>(password.size());
bool lower = false;
bool upper = false;
bool digit = false;
for (char c : password) {
lower |= c >= 'a' && c <= 'z';
upper |= c >= 'A' && c <= 'Z';
digit |= c >= '0' && c <= '9';
}
int missing = !lower + !upper + !digit;
std::vector<int> runs;
for (int i = 0; i < n;) {
int j = i;
while (j < n && password[j] == password[i]) ++j;
if (j - i >= 3) runs.push_back(j - i);
i = j;
}
int replacements = 0;
for (int length : runs) replacements += length / 3;
if (n < 6) return std::max(6 - n, missing);
if (n <= 20) return std::max(missing, replacements);
int deletions = n - 20;
for (int remainder = 0; remainder < 3; ++remainder) {
for (int& length : runs) {
if (deletions == 0 || length % 3 != remainder) {
continue;
}
int need = remainder == 0 ? 1
: (remainder == 1 ? 2 : 3);
int use = std::min(deletions, need);
int before = length / 3;
length -= use;
deletions -= use;
replacements -= before - length / 3;
}
}
replacements -= deletions / 3;
return (n - 20) + std::max(missing, replacements);
}
};
代码分析¶
删除顺序按“每个删除能节省多少次替换”排序,优先消除最便宜的一次替换;未用于降低替换数的剩余删除仍然必须执行,但不会改变替换需求。短密码分支单独处理插入与类别缺失的重叠收益。设密码长度为 n,扫描和重复段处理为 O(n),额外空间为 O(n)。