420. 强密码检验器

exiaohu 于 2022-04-02 发布

题目链接：420. 强密码检验器

复杂模拟，分类讨论：

  1. 当密码长度过短时，需要的最小操作次数是添加字符的次数（为了满足长度条件），和替换字符（为了满足种类条件）次数的较大值，因为此时不连续出现条件很容易满足；
  2. 当密码长度符合要求时，需要的最小操作次数是为了满足种类条件和不连续出现条件，所需要替换字符的次数的较大值；
  3. 当密码长度过长时：
    • 为了满足长度条件，需要移除一些字符，在移除字符的过程中，优先移除连续出现的字符
      • 为了更少操作，先移除连续出现次数为 3, 6, 9 这样数字的字符，再移除连续出现次数为 4, 7, 10 这样数字的字符，最后再移除出现次数为 5, 8, 11 这样数字的字符）；
    • 当满足长度条件后，问题变成上述第 2 种情况。
import itertools
import re


class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        size = len(password)
        kinds = (1 if re.search('[a-z]', password) else 0) + \
                (1 if re.search('[A-Z]', password) else 0) + \
                (1 if re.search('[0-9]', password) else 0)

        if size < 6:
            return max(6 - size, 3 - kinds)
        elif size <= 20:
            return max(len(re.findall(r'(.)\1\1', password)), 3 - kinds)
        else:
            # 做减法的数量是 size - 20
            # 做替换的数量是 3 - kinds

            repeat = [[], [], []]
            for mo in re.finditer(r'(.)\1{2,}', password):
                l, r = mo.span()
                repeat[(r - l) % 3].append(r - l)

            def apply_remove(n: int):
                while n:
                    if repeat[0]:
                        v = repeat[0].pop()
                        if v > 3:
                            repeat[2].append(v - 1)
                    elif repeat[1]:
                        v = repeat[1].pop()
                        repeat[0].append(v - 1)
                    elif repeat[2]:
                        v = repeat[2].pop()
                        repeat[1].append(v - 1)
                    else:
                        return n

                    n -= 1
                return 0

            apply_remove(size - 20)

            return size - 20 + max(3 - kinds, sum(v // 3 for v in itertools.chain(*repeat)))