0420：强密码检验器（★★）

力扣第 420 题

题目

满足以下条件的密码被认为是强密码：

• 由至少 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 由字母、数字、点 '.' 或者感叹号 '!' 组成

相似问题：

• 2299：强密码检验器 II（1241 分）

分析

先得到必须补充的字符个数 lack，然后按密码长度 n 分类讨论：

• n<6
  • 可以再按 n=5 和 n<5 分类考虑，结果都满足 max(6-n, lack)
• 6<=n<=20
  • 对于任一连续段长度 a，用 a//3 步替换操作即可满足条件“同一字符不连续出现三次 ”
  • 最后取 max(替换操作, lack)即可
• n>20，必须进行删除操作
  • 优先删除连续段的字符，而且优先删除长度 a%3=0 的连续段，从而减少之后的替换操作
  • 于是考虑用堆，每轮选 a%3 最小的 a 进行删除操作，直到没有连续段长度 >=3 或 n=20
  • 删除完成后，就转为上一情况了

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        n = len(password)
        lack = 3-sum(bool(re.search(reg,password)) for reg in ['[a-z]','[A-Z]','[0-9]'])
        if n<6:
            return max(6-n,lack)
        pq = []
        for _, g in groupby(password):
            a = len(list(g))
            if a>=3:
                heappush(pq, (a%3, a))
        res = 0
        while pq and n>20:
            _, a = heappop(pq)
            if a-1>=3:
                heappush(pq, ((a-1)%3, a-1))
            n -= 1
            res += 1
        return res+max(0,n-20)+max(sum(a//3 for _,a in pq),lack)

33 ms