Strong Password Checker

Problem Id: 420 Difficulty: Hard


Intuition

Solution


class Solution:
    def _types(self, s):
        types = [0, 0, 0]
        for c in s:
            if c in string.ascii_uppercase:
                types[0] += 1
            elif c in string.ascii_lowercase:
                types[1] += 1
            elif c in string.digits:
                types[2] += 1
        return types

    def _repeated(self, s):
        tmp_i = 0
        repeated_length = {}
        for i, c in enumerate(s):
            if s[tmp_i] != c:
                tmp_i = i
            if i - tmp_i + 1 >= 3:
                repeated_length[tmp_i] = i - tmp_i + 1
        return repeated_length

    def strongPasswordChecker(self, s: str) -> int:
        """
        1. Remove or add
        2. replace
        """
        ans = 0
        # Remove
        while len(s) > 20:
            # Remove ...aa[a]..., ..aa[a]aaa.., then ..aaaa[a]..
            tmp_i = 0
            repeated_length = {}
            for i, c in enumerate(s):
                if s[tmp_i] != c:
                    tmp_i = i
                if i - tmp_i + 1 >= 3:
                    repeated_length[tmp_i] = i - tmp_i + 1
            # Remove %3 == 0 first then 1 then 2
            flag = False
            for tmp in range(3):
                if flag:
                    break
                for k in repeated_length:
                    if repeated_length[k] % 3 == tmp:
                        s = s[:k] + s[k+1:]
                        ans += 1
                        flag = True
                        break
            if flag:
                continue
            # Remove any char in the same type
            types = [0, 0, 0]
            for i, c in enumerate(s):
                if c in string.ascii_uppercase:
                    types[0] += 1
                elif c in string.ascii_lowercase:
                    types[1] += 1
                elif c in string.digits:
                    types[2] += 1
                if 2 in types:
                    s = s[:i] + s[i+1:]
                    ans += 1
                    flag = True
                    break
            if not flag:
                break
        # Insert
        while len(s) < 6:
            types = self._types(s)
            if types[0] == 0:
                tmp = 'A'
            elif types[1] == 0:
                tmp = 'a'
            elif types[2] == 0:
                tmp = '0'
            else:
                tmp = None
            repeated = self._repeated(s)
            if repeated:
                i = list(repeated.keys())[0] + 2
            else:
                i = 0
            if tmp is None:
                tmp = 'A' if s[i] == 'a' else 'a'
            s = s[:i] + tmp + s[i:]
            ans += 1
        # Replace
        while True:
            types = self._types(s)
            if types[0] == 0:
                new = 'A'
            elif types[1] == 0:
                new = 'a'
            elif types[2] == 0:
                new = '0'
            else:
                new = None

            tmp_i = 0
            repeated_length = self._repeated(s)
            if new is None and not repeated_length:
                break
            if repeated_length:
                i = list(repeated_length.keys())[0] + 2
                if new is None:
                    new = 'A' if s[i] == 'a' else 'a'
                s = s[:i] + new + s[i+1:]
                ans += 1
                continue
            else:
                s += new
                ans += 1
                continue
        return ans