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

class Solution:
    def strongPasswordChecker(self, password: str) -> int:

        # Step 1: Identify missing character types
        missing_types = 3
        if re.search(r'[a-z]', password):
            missing_types -= 1
        if re.search(r'[A-Z]', password):
            missing_types -= 1
        if re.search(r'\d', password):
            missing_types -= 1

        n = len(password)
        repeats = []
        i = 2
        s = list(password)
        
        # Step 2: Find sequences of repeating characters
        while i < n:
            if s[i] == s[i - 1] == s[i - 2]:
                start = i - 2
                while i < n and s[i] == s[i - 1]:
                    i += 1
                repeats.append(i - start)
            else:
                i += 1

        if n < 6:
            # Password is too short; insertions are needed
            return max(missing_types, 6 - n)
        else:
            over_len = max(n - 20, 0)
            deletions = over_len
            replacements = 0
            
            # Step 3: Organize repeats based on their mod 3 value
            import heapq
            heap = []
            for r in repeats:
                heapq.heappush(heap, (r % 3, r))
            
            # Step 4: Apply deletions optimally to reduce replacements
            while heap and over_len > 0:
                mod, r = heapq.heappop(heap)
                if r >= 3:
                    if mod == 0:
                        reduce = min(over_len, 1)
                    elif mod == 1:
                        reduce = min(over_len, 2)
                    else:  # mod == 2
                        reduce = min(over_len, 3)
                    over_len -= reduce
                    r -= reduce
                    heapq.heappush(heap, (r % 3, r))
            
            # Step 5: Calculate replacements after deletions
            while heap:
                mod, r = heapq.heappop(heap)
                if r >= 3:
                    replacements += r // 3

            # Step 6: Calculate total steps
            if n <= 20:
                return max(missing_types, replacements)
            else:
                return deletions + max(missing_types, replacements)
16500