题目:
题解:
class Solution:def strongPasswordChecker(self, password: str) -> int:n = len(password)has_lower = has_upper = has_digit = Falsefor ch in password:if ch.islower():has_lower = Trueelif ch.isupper():has_upper = Trueelif ch.isdigit():has_digit = Truecategories = has_lower + has_upper + has_digitif n < 6:return max(6 - n, 3 - categories)elif n <= 20:replace = cnt = 0cur = "#"for ch in password:if ch == cur:cnt += 1else:replace += cnt // 3cnt = 1cur = chreplace += cnt // 3return max(replace, 3 - categories)else:# 替换次数和删除次数replace, remove = 0, n - 20# k mod 3 = 1 的组数,即删除 2 个字符可以减少 1 次替换操作rm2 = cnt = 0cur = "#"for ch in password:if ch == cur:cnt += 1else:if remove > 0 and cnt >= 3:if cnt % 3 == 0:# 如果是 k % 3 = 0 的组,那么优先删除 1 个字符,减少 1 次替换操作remove -= 1replace -= 1elif cnt % 3 == 1:# 如果是 k % 3 = 1 的组,那么存下来备用rm2 += 1# k % 3 = 2 的组无需显式考虑replace += cnt // 3cnt = 1cur = chif remove > 0 and cnt >= 3:if cnt % 3 == 0:remove -= 1replace -= 1elif cnt % 3 == 1:rm2 += 1replace += cnt // 3# 使用 k % 3 = 1 的组的数量,由剩余的替换次数、组数和剩余的删除次数共同决定use2 = min(replace, rm2, remove // 2)replace -= use2remove -= use2 * 2# 由于每有一次替换次数就一定有 3 个连续相同的字符(k / 3 决定),因此这里可以直接计算出使用 k % 3 = 2 的组的数量use3 = min(replace, remove // 3)replace -= use3remove -= use3 * 3return (n - 20) + max(replace, 3 - categories)