难度: Hard
满足以下条件的密码被认为是强密码：
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 <= 50password 由字母、数字、点 '.' 或者感叹号 '!' 组成运行时间: 28 ms
内存: 0.0 MB
import itertools
class Solution:
lowercase = set('abcdefghijklmnopqrstuvwxyz')
uppercase = set('ABCDEFGHIJKLMNOPQRSTUFVWXYZ')
digit = set('0123456789')
def strongPasswordChecker(self, s: str) -> int:
characters = set(s)
# Check rule (2)
needs_lowercase = not (characters & self.lowercase)
needs_uppercase = not (characters & self.uppercase)
needs_digit = not (characters & self.digit)
num_required_type_replaces = int(needs_lowercase + needs_uppercase + needs_digit)
# Check rule (1)
num_required_inserts = max(0, 6 - len(s))
num_required_deletes = max(0, len(s) - 20)
# Check rule (3)
# Convert s to a list of repetitions for us to manipulate
# For s = '11aaabB' we have groups = [2, 3, 1, 1]
groups = [len(list(grp)) for _, grp in itertools.groupby(s)]
# We apply deletions iteratively and always choose the best one.
# This should be fine for short passwords :)
# A delete is better the closer it gets us to removing a group of three.
# Thus, a group needs to be (a) larger than 3 and (b) minimal wrt modulo 3.
def apply_best_delete():
argmin, _ = min(
enumerate(groups),
# Ignore groups of length < 3 as long as others are available.
key=lambda it: it[1] % 3 if it[1] >= 3 else 10 - it[1],
)
groups[argmin] -= 1
for _ in range(num_required_deletes):
apply_best_delete()
# On the finished groups, we need one repace per 3 consecutive letters.
num_required_group_replaces = sum(
group // 3
for group in groups
)
return (
# Deletes need to be done anyway
num_required_deletes
# Type replaces can be eaten up by inserts or group replaces.
# Note that because of the interplay of rules (1) and (2), the required number of group replaces
# can never be greater than the number of type replaces and inserts for candidates of length < 6.
+ max(
num_required_type_replaces,
num_required_group_replaces,
num_required_inserts,
)
)
这个题解的思路是分别检查密码是否满足三条规则： 1. 检查密码长度是否在6到20之间，计算需要插入或删除的字符数。 2. 检查密码是否包含小写字母、大写字母和数字，计算需要替换的字符数。 3. 将密码转换为连续字符的分组列表，迭代地应用删除操作，使得尽可能消除连续三个相同字符的情况。最后计算需要替换的分组数。 最终返回所需的最少修改步数，即删除操作数 + max(需要的类型替换数, 需要的分组替换数, 需要的插入数)。
时间复杂度: O(n * num_required_deletes)
空间复杂度: O(n)
```python
import itertools
class Solution:
lowercase = set('abcdefghijklmnopqrstuvwxyz')
uppercase = set('ABCDEFGHIJKLMNOPQRSTUFVWXYZ')
digit = set('0123456789')
def strongPasswordChecker(self, s: str) -> int:
characters = set(s)
# 检查规则(2)，计算需要的类型替换数
needs_lowercase = not (characters & self.lowercase)
needs_uppercase = not (characters & self.uppercase)
needs_digit = not (characters & self.digit)
num_required_type_replaces = int(needs_lowercase + needs_uppercase + needs_digit)
# 检查规则(1)，计算需要的插入数和删除数
num_required_inserts = max(0, 6 - len(s))
num_required_deletes = max(0, len(s) - 20)
# 检查规则(3)
# 将密码转换为连续字符的分组列表
groups = [len(list(grp)) for _, grp in itertools.groupby(s)]
# 迭代地应用最佳的删除操作
def apply_best_delete():
argmin, _ = min(
enumerate(groups),
# 忽略长度小于3的分组，除非没有其他选择
key=lambda it: it[1] % 3 if it[1] >= 3 else 10 - it[1],
)
groups[argmin] -= 1
for _ in range(num_required_deletes):
apply_best_delete()
# 计算需要的分组替换数
num_required_group_replaces = sum(
group // 3
for group in groups
)
return (
# 删除操作数
num_required_deletes
# 类型替换数可以被插入数或分组替换数替代
+ max(
num_required_type_replaces,
num_required_group_replaces,
num_required_inserts,
)
)
```
对于长度小于6的密码，优先考虑插入操作，因为密码需要至少6个字符满足基本长度要求。如果同时缺少必要的字符类型（如大写、小写或数字），可以通过插入缺失类型的字符来同时解决两个问题。对于长度大于20的密码，首先考虑删除多余的字符以减少长度。在这个过程中，如果存在连续三个相同的字符，优先删除这些字符以减少需要的替换次数。替换操作主要用于同时调整字符类型和解决三个连续字符的问题，特别是当密码长度正好在6到20之间时。总的来说，选择哪种操作取决于同时满足所有密码规则的最小修改步数。
选择删除字符数目为'group % 3'的分组是因为这种分组最容易通过删除一个字符就减少需要的替换次数。例如，一个长度为5的分组（group % 3 == 2）通过删除一个字符可以变为长度4，这样只需替换一次即可解决连续字符问题（而不是两次）。这种策略最小化了总的修改步数，因为它减少了连续字符组需要的替换次数。
是否替换或删除字符取决于密码的总长度和连续字符的分组长度。如果密码长度超过20，优先考虑删除字符以减少总长度。如果密码长度较短或正好，考虑替换字符来打破连续性，尤其是当连续分组较短（如恰好3个字符）时。替换可以同时解决连续字符和字符多样性的问题。总体策略是选择可以同时最大程度减少修改次数和满足所有规则的操作。
为了确保总的修改次数最少，需要综合考虑所有规则并选择最优的操作策略。这通常涉及到优化操作的顺序和类型。例如，通过优先执行删除操作来调整长度，可以减少后续可能需要的替换次数。在插入时选择缺失的字符类型，可以同时解决长度和字符多样性的问题。最终，选择操作时要以满足所有密码规则的最小总修改次数为目标。具体实施时可能需要动态调整策略，根据当前密码的状态来选择最合适的操作。