1.题目基本信息
1.1.题目描述
满足以下条件的密码被认为是强密码：
-
由至少 6 个，至多 20 个字符组成。
-
包含至少 一个小写 字母，至少 一个大写 字母，和至少 一个数字 。
-
不包含连续三个重复字符 (比如 "Baaabb0" 是弱密码, 但是 "Baaba0" 是强密码)。
给你一个字符串 password ，返回 将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 0 。
在一步修改操作中，你可以：
-
插入一个字符到 password ，
-
从 password 中删除一个字符，或
-
用另一个字符来替换 password 中的某个字符。
1.2.题目地址
https://leetcode.cn/problems/strong-password-checker/description/
2.解题方法
2.1.解题思路
模拟+分类讨论
时间复杂度：O(n)
2.2.解题步骤
第一步，记n=len(password)，计算总共有小写、大写、数字这三类中几类，使用categories进行记录
第二步，讨论n<6的情况。此时仅「添加一个字符」是有意义的。result=max(6-n,3-categories)
第三步，讨论6<=n<=20的情况。此时仅「替换一个字符」是有意义的。假设连续相同的子串中字符数为cnt(ch)，则此时需要替换的次数=sum(cnt(ch)//3 for ch in set(password))
第四步，讨论n>20的情况。此时仅「替换一个字符」和「删除一个字符」这俩操作是有意义的。如果cnt(ch)%3==0，则能够删除一个，同时减少一次替换（能删则删，保证在20之内），如果cnt(ch)%3==1，则能够删除两个
-
4.1.构建维护变量。使用replace维护当前的替换个数；remove维护当前至少需要删除的个数；rm2维护cnt(ch)%3==1的组数
-
4.2.贪心的用cnt(ch)%3==0的组进行删除一个和替换cnt(ch)//3个
-
4.3.处理cnt(ch)//3==1的组，贪心的选择需要删除的个数
-
4.4.处理cnt(ch)//3==2的组，贪心的选择需要删除的个数
-
4.5.n-20是至少需要删除的个数（remove有剩余也是这么多）；max(replace,3-categories)为连续重复的子串中，至少需要替换的个数（已经将末尾该删除的进行贪心删除了）
3.解题代码
python代码
class Solution:
def strongPasswordChecker(self, password: str) -> int:
# 思路：模拟+分类讨论
n = len(password)
# 第一步，记n=len(password)，计算总共有小写、大写、数字这三类中几类，使用categories进行记录
haveLower, haveUpper, haveDigit = False, False, False
for ch in password:
if ch.islower():
haveLower = True
elif ch.isupper():
haveUpper = True
elif ch.isdigit:
haveDigit = True
categories = haveLower + haveUpper + haveDigit
if n < 6:
# 第二步，讨论n<6的情况。此时仅「添加一个字符」是有意义的。result=max(6-n,3-categories)
return max(6 - n, 3 - categories)
elif n <= 20:
# 第三步，讨论6<=n<=20的情况。此时仅「替换一个字符」是有意义的。假设连续相同的子串中字符数为cnt(ch)，则此时需要替换的次数=sum(cnt(ch)//3 for ch in set(password))
result = 0
cur = "#"
cnt = 0
for ch in password + "#":
if ch == cur:
cnt += 1
else:
result += cnt // 3
cur = ch
cnt = 1
return result
else:
# 第四步，讨论n>20的情况。此时仅「替换一个字符」和「删除一个字符」这俩操作是有意义的。如果cnt(ch)%3==0，则能够删除一个，同时减少一次替换（能删则删，保证在20之内），如果cnt(ch)%3==1，则能够删除两个
# 4.1.构建维护变量。使用replace维护当前的替换个数；remove维护当前至少需要删除的个数；rm2维护cnt(ch)%3==1的组数
replace, remove = 0, n - 20
rm2 = 0
# 4.2.贪心的用cnt(ch)%3==0的组进行删除一个和替换cnt(ch)//3个
cur = "#"
cnt = 0
for ch in password + "#":
if ch == cur:
cnt += 1
else:
if remove > 0 and cnt >= 3:
if cnt % 3 == 0:
replace -= 1
remove -= 1
elif cnt % 3 == 1:
rm2 += 1
replace += cnt // 3
cur = ch
cnt = 1
# 4.3.处理cnt(ch)//3==1的组，贪心的选择需要删除的个数
use2 = min(rm2, remove // 2)
replace -= use2
remove -= 2 * use2
# 4.4.处理cnt(ch)//3==2的组，贪心的选择需要删除的个数
use3 = remove // 3
replace -= use3
remove -= 3 * use3
# 4.5.n-20是至少需要删除的个数（remove有剩余也是这么多）；max(replace,3-categories)为连续重复的子串中，至少需要替换的个数（已经将末尾该删除的进行贪心删除了）
return (n - 20) + max(replace, 3 - categories)4.执行结果
