420.md

420. Strong Password Checker

Solution 1 (time O(n), space O(1))

class Solution(object):
    def strongPasswordChecker(self, password):
        """
        :type password: str
        :rtype: int
        """
        n = len(password)
        A, B, C = 0, 0, 0
        for c in password:
            if ord(c) >= ord("a") and ord(c) <= ord("z"):
                A = 1
            elif ord(c) >= ord("1") and ord(c) <= ord("9"):
                B = 1
            elif ord(c) >= ord("A") and ord(c) <= ord("Z"):
                C = 1
        m = A + B + C
        if n < 6:
            return max(6 - n, 3 - m)
        elif n <= 20:
            cnt = 0
            p1 = 0
            while p1 < n:
                p2 = p1
                while p2 < n and password[p2] == password[p1]:
                    p2 += 1
                cnt += (p2 - p1) // 3
                p1 = p2
            return max(cnt, 3 - m)
        else:
            cnt = 0
            cnts = [0, 0, 0]
            p1 = 0
            while p1 < n:
                p2 = p1
                while p2 < n and password[p2] == password[p1]:
                    p2 += 1
                if p2 - p1 >= 3:
                    cnt += (p2 - p1) // 3
                    cnts[(p2 - p1) % 3] += 1
                p1 = p2
            base = n - 20
            cur = base
            for i in range(3):
                if i == 2:
                    cnts[i] = cnt
                if cnts[i] != 0 and cur != 0:
                    t = min(cnts[i] * (i + 1), cur)
                    cur -= t
                    cnt -= t / (i + 1)
            return base + max(cnt, 3 - m)