目录

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

相似问题:

分析

先得到必须补充的字符个数 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