<p>A password is considered strong if the below conditions are all met:</p>

<ul>
	<li>It has at least <code>6</code> characters and at most <code>20</code> characters.</li>
	<li>It contains at least <strong>one lowercase</strong> letter, at least <strong>one uppercase</strong> letter, and at least <strong>one digit</strong>.</li>
	<li>It does not contain three repeating characters in a row (i.e., <code>&quot;B<u><strong>aaa</strong></u>bb0&quot;</code> is weak, but <code>&quot;B<strong><u>aa</u></strong>b<u><strong>a</strong></u>0&quot;</code> is strong).</li>
</ul>

<p>Given a string <code>password</code>, return <em>the minimum number of steps required to make <code>password</code> strong. if <code>password</code> is already strong, return <code>0</code>.</em></p>

<p>In one step, you can:</p>

<ul>
	<li>Insert one character to <code>password</code>,</li>
	<li>Delete one character from <code>password</code>, or</li>
	<li>Replace one character of <code>password</code> with another character.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> password = "a"
<strong>Output:</strong> 5
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> password = "aA1"
<strong>Output:</strong> 3
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> password = "1337C0d3"
<strong>Output:</strong> 0
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= password.length &lt;= 50</code></li>
	<li><code>password</code> consists of letters, digits, dot&nbsp;<code>&#39;.&#39;</code> or exclamation mark <code>&#39;!&#39;</code>.</li>
</ul>

class Solution:

    def getstats(self, password):
        cdigit = 0
        clower = 0
        cupper = 0
        for e in password:
            e = ord(e)
            if e >= 97 and e <= 122:
                clower += 1
            if e >= 65 and e <= 90:
                cupper += 1
            if e >= 48 and e <= 57:
                cdigit += 1
        threecon = []
        i = 0
        while i+2 < len(password):
            if password[i] == password[i+1] == password[i+2]:
                threecon.append(i+2)
                i += 3
            else:
                i += 1
        return (cdigit, clower, cupper, threecon)
    def getdifferentchar(self, var1, var2, cdigit, clower, cupper):
        choices = []
        if cdigit == 0:
            for e in range(48, 57 + 1):
                choices.append(e)
        if clower == 0:
            for e in range(97, 122 + 1):
                choices.append(e)
        if cupper == 0:
            for e in range(65, 90 + 1):
                choices.append(e)
        if cdigit >= 1 and clower >= 1 and cupper >= 1:
            for e in range(48, 57 + 1):
                choices.append(e)
            for e in range(97, 122 + 1):
                choices.append(e)
            for e in range(65, 90 + 1):
                choices.append(e)
        if ord(var1) in choices:
            choices.remove(ord(var1))
        if ord(var2) in choices:
            choices.remove(ord(var2))
        return str(chr(choices[0]))
    def optimalreplace(self, password, cdigit, clower, cupper, threecon):
        # only to be called when length <= 20 and >= 6
        cost = 0
        if len(threecon) > 0:
            for e in threecon:
                char = self.getdifferentchar(password[e+1] if e+1 < len(password) else password[e], password[e], cdigit, clower, cupper)
                password[e] = char
                cdigit, clower, cupper, threecon = self.getstats(password)
                cost += 1
        cdigit, clower, cupper, threecon = self.getstats(password)
        # Assumes we can get it done by replacing
        if cdigit == 0:
            idx = -1
            for i, e in enumerate(password):
                if clower > 1:
                    if ord(e) >= 97 and ord(e) <= 122:
                        idx = i
                        clower -= 1
                        break
                elif cupper > 1:
                    if ord(e) >= 65 and ord(e) <= 90:
                        idx = i
                        cupper -= 1
                        break
                else:
                    if not e.islower() and not e.isupper():
                        idx = i
                        break
            password[idx] = self.getdifferentchar(password[idx+1] if idx+1 < len(password) else password[idx], password[idx], cdigit, clower, cupper)
            cdigit = 1
            cost += 1
        if clower == 0:
            idx = -1
            for i, e in enumerate(password):
                if cdigit > 1:
                    if ord(e) >= 48 and ord(e) <= 57:
                        idx = i
                        cdigit -= 1
                        break
                elif cupper > 1:
                    if ord(e) >= 65 and ord(e) <= 90:
                        idx = i
                        cupper -= 1
                        break
                else:
                    if not e.islower() and not e.isupper():
                        idx = i
                        break
            password[idx] = self.getdifferentchar(password[idx+1] if idx+1 < len(password) else password[idx], password[idx], cdigit, clower, cupper)
            clower = 1
            cost += 1
        if cupper == 0:
            idx = -1
            for i, e in enumerate(password):
                if cdigit > 1:
                    if ord(e) >= 48 and ord(e) <= 57:
                        idx = i
                        cdigit -= 1
                        break
                elif clower > 1:
                    if ord(e) >= 97 and ord(e) <= 122:
                        idx = i
                        clower -= 1
                        break
                else:
                    if not e.islower() and not e.isupper():
                        idx = i
                        break
            password[idx] = self.getdifferentchar(password[idx+1] if idx+1 < len(password) else password[idx], password[idx], cdigit, clower, cupper)
            cupper = 1
            cost += 1
        return (password, cost)
    def optimalremove(self, password, cdigit, clower, cupper):
        if cdigit == 0 and clower == 0 and cupper == 0:
            return (password[:20], len(password) - 20)
        k = max(len(password)-20, 0)
        cost = k
        # If there are consecutive blocks, remove them (until k is enough) first
        temp = []
        idx = 0
        p = password
        while idx+1 < len(p):
            if p[idx] == p[idx+1]:
                idx += 1
            else:
                temp.append(p[:idx+1])
                p = p[idx+1:]
                idx = 0
        temp.append(p)

        ###

        # First chunk you delete should be the ones with len(temp[i])%3==0, then 1, then 2, then again if possible(since we always delete some elements, it is possible to get len%3==0 again, or 1, or 2)
        # By doing this until k is finished or all 3 length chunks eliminated, then you can use my following code to delete characters one by one safely
        while k > 0 and sum(1 if len(x)>=3 else 0 for x in temp) > 0:
            count = 0
            for remainder in range(3):
                for i in range(len(temp)):
                    if len(temp[i])%3 == remainder and len(temp[i]) >= 3 and k >= remainder + 1:
                        temp[i] = temp[i][:-(remainder+1)]
                        k -= (remainder+1)
                        count += 1
            if count == 0:# nothing changed so break out of while loop
                break
        ###
        
        password = "".join("".join(x) for x in temp)
        cdigit, clower, cupper, _ = self.getstats(password)
        # If there is no consecutive blocks(more than or equal to 3), then we can delete safely one by one
        if cdigit > 1:
            skip = set()
            while cdigit > 1 and k > 0 and len(skip) != cdigit:
                idx = 0
                while idx < len(password) and (not (ord(password[idx]) >= 48 and ord(password[idx]) <= 57) or idx in skip):
                    idx += 1
                if (idx-1 > -1 and idx+2 < len(password) and password[idx-1] == password[idx+1] == password[idx+2]) or (idx-2 > -1 and idx+1 < len(password) and password[idx-2] == password[idx-1] == password[idx+1]):
                    skip.add(idx)
                else:
                    password = password[:idx] + password[idx+1:]
                    k -= 1
                    cdigit -= 1
        if clower > 1:
            skip = set()
            while clower > 1 and k > 0 and len(skip) != clower:
                idx = 0
                while idx < len(password) and (not (ord(password[idx]) >= 97 and ord(password[idx]) <= 122) or idx in skip):
                    idx += 1
                if (idx-1 > -1 and idx+2 < len(password) and password[idx-1] == password[idx+1] == password[idx+2]) or (idx-2 > -1 and idx+1 < len(password) and password[idx-2] == password[idx-1] == password[idx+1]):
                    skip.add(idx)
                else:
                    password = password[:idx] + password[idx+1:]
                    k -= 1
                    clower -= 1
        if cupper > 1:
            skip = set()
            while cupper > 1 and k > 0 and len(skip) != cupper:
                idx = 0
                while idx < len(password) and (not (ord(password[idx]) >= 65 and ord(password[idx]) <= 90) or idx in skip):
                    idx += 1
                if (idx-1 > -1 and idx+2 < len(password) and password[idx-1] == password[idx+1] == password[idx+2]) or (idx-2 > -1 and idx+1 < len(password) and password[idx-2] == password[idx-1] == password[idx+1]):
                    skip.add(idx)
                else:
                    password = password[:idx] + password[idx+1:]
                    k -= 1
                    cupper -= 1
        
        return ([x for x in password], cost)
            
    def optimalinsert(self, password, cdigit, clower, cupper, threecon):
        cost = 6 - len(password)

        while len(threecon) > 0 and len(password) < 6:
            password.insert(threecon[-1], self.getdifferentchar(password[threecon[-1]], password[threecon[-1]], cdigit, clower, cupper))
            cdigit, clower, cupper, _ = self.getstats(password)
            threecon.pop(-1)
        iterate_to = 6 - len(password)
        for _ in range(iterate_to):
            password += self.getdifferentchar(password[-1], password[-1], cdigit, clower, cupper)
            cdigit, clower, cupper, _ = self.getstats(password)
        
        return (password, cost)
        
    def strongPasswordChecker(self, password: str) -> int:
        globalmincost = [float("+inf")]
        cost = 0
        password = [x for x in password]
        if len(password) > 20:
            cdigit, clower, cupper, threecon = self.getstats(password.copy())
            password1 = password.copy()
            password1, inccost = self.optimalremove(password1.copy(), cdigit, clower, cupper)
            cost += inccost
            password = password1

        if len(password) < 6:
            cdigit, clower, cupper, threecon = self.getstats(password.copy())
            password2 = password.copy()
            password2, inccost = self.optimalinsert(password2.copy(), cdigit, clower, cupper, threecon)
            cost += inccost
            password = password2

        cdigit, clower, cupper, threecon = self.getstats(password.copy())
        if len(threecon) > 0:
            cdigit, clower, cupper, threecon = self.getstats(password.copy())
            password3 = password.copy()
            password3, inccost = self.optimalreplace(password3.copy(), cdigit, clower, cupper, threecon)
            cost += inccost
            password = password3

        
        cdigit, clower, cupper, threecon = self.getstats(password)
        return cost + ((1 if cdigit == 0 else 0)+(1 if clower == 0 else 0)+(1 if cupper == 0 else 0))
17200