<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>

import string
import heapq
from collections import Counter
class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        contains_lower = any(char in string.ascii_lowercase for char in password)
        contains_upper = any(char in string.ascii_uppercase for char in password)
        contains_digit = any(char in string.digits for char in password)

        if len(password) < 5:
            return 6 - len(password)
        elif len(password) == 5:
            return 1 if contains_lower + contains_upper + contains_digit >= 2 else 2
        else:
            seq_list = []
            last_char = None
            char_count = 0

            for char in password:
                if char == last_char:
                    char_count += 1
                else:
                    if char_count >= 3:
                        seq_list.append(char_count)

                    last_char = char
                    char_count = 1

            if char_count >= 3:
                seq_list.append(char_count)
            
            char_type_changes = 3 - contains_lower - contains_upper - contains_digit
            total_changes = 0
            for seq in seq_list:
                total_changes += seq // 3

            if len(password) <= 20:
                return max(total_changes, char_type_changes)
            else:
                total_ct = len(password)
                seq_tups = [(length % 3, length) for length in seq_list]
                heapify(seq_tups)
                ct_remaining = total_ct - 20
                for _ in range(total_ct-20):
                    if len(seq_tups) == 0:
                        break
                    _, length = heapq.heappop(seq_tups)
                    if length-1 >= 3:
                        heapq.heappush(seq_tups, ((length-1) % 3, length-1))
                    ct_remaining -= 1
                

                total_changes = sum(length // 3 for (_, length) in seq_tups)
                return total_ct-20 + max(total_changes, char_type_changes)

                        

16600