满足以下条件的密码被认为是强密码:
由至少 6 个,至多 20 个字符组成。
包含至少 一个小写 字母,至少 一个大写 字母,和至少 一个数字 。
不包含连续三个重复字符 (比如 “Baaabb0” 是弱密码, 但是 “Baaba0” 是强密码)。
给你一个字符串 password ,返回 将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码,则返回 0 。
在一步修改操作中,你可以:
插入一个字符到 password ,
从 password 中删除一个字符,或
用另一个字符来替换 password 中的某个字符。
示例 1:
输入:password = “a”
输出:5
示例 2:
输入:password = “aA1”
输出:3
示例 3:
输入:password = “1337C0d3”
输出:0
提示:
1 <= password.length <= 50
password 由字母、数字、点 ‘.’ 或者感叹号 ‘!’ 组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/strong-password-checker
方法一:分类讨论
C++提交内容:
class Solution {
public:int strongPasswordChecker(string password) {int n = password.size();bool has_lower = false, has_upper = false, has_digit = false;for (char ch: password) {if (islower(ch)) {has_lower = true;}else if (isupper(ch)) {has_upper = true;}else if (isdigit(ch)) {has_digit = true;}}int categories = has_lower + has_upper + has_digit;if (n < 6) {return max(6 - n, 3 - categories);}else if (n <= 20) {int replace = 0;int cnt = 0;char cur = '#';for (char ch: password) {if (ch == cur) {++cnt;}else {replace += cnt / 3;cnt = 1;cur = ch;}}replace += cnt / 3;return max(replace, 3 - categories);}else {int replace = 0, remove = n - 20;int rm2 = 0;int cnt = 0;char cur = '#';for (char ch: password) {if (ch == cur) {++cnt;}else {if (remove > 0 && cnt >= 3) {if (cnt % 3 == 0) {--remove;--replace;}else if (cnt % 3 == 1) {++rm2;}}replace += cnt / 3;cnt = 1;cur = ch;}}if (remove > 0 && cnt >= 3) {if (cnt % 3 == 0) {--remove;--replace;}else if (cnt % 3 == 1) {++rm2;}}replace += cnt / 3;int use2 = min({replace, rm2, remove / 2});replace -= use2;remove -= use2 * 2;int use3 = min({replace, remove / 3});replace -= use3;remove -= use3 * 3;return (n - 20) + max(replace, 3 - categories);}}
};