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

from enum import Enum
from typing import TypedDict

Cats = TypedDict("Cats", {"name": str, "age": int})

MAX_LENGTH = 20
MIN_LENGTH = 6

Char = Enum("Char", "UPPER LOWER DIGIT OTHER")


def to_char(c: str) -> Char:
    os = ord(c)
    if os >= ord("A") and os <= ord("Z"):
        return Char.UPPER
    if os >= ord("a") and os <= ord("z"):
        return Char.LOWER
    if os >= ord("0") and os <= ord("9"):
        return Char.DIGIT

    return Char.OTHER


class Solver:
    def __init__(self, password: str) -> None:
        self.password = password
        self.length = len(password)
        self.steps = 0
        self.categories = {
            Char.UPPER: 0,
            Char.LOWER: 0,
            Char.DIGIT: 0,
            Char.OTHER: 0,
        }
        self.sequences: list[tuple[int, int]] = []

        self.init_props()

    def init_props(self) -> None:
        start = -1
        p0 = None
        p1 = None

        for i in range(self.length):
            c = self.password[i]
            self.categories[to_char(c)] += 1

            if start == -1 and p0 == p1 == c:
                start = i - 2
            elif start > -1 and c != p1:
                self.sequences.append((start, i))
                start = -1

            p0 = p1
            p1 = c

        if start > -1:
            self.sequences.append((start, self.length))

    def solve(self) -> int:
        if self.length > MAX_LENGTH:
            self.shorten_repeats()
            self.shorten_most_used()
        elif self.length < MIN_LENGTH:
            self.lengthen()

        self.fix()

        return self.steps

    def least_used_cat_char(self) -> Char:
        return min(
            [e for e in self.categories.items() if e[0] != Char.OTHER],
            key=lambda x: x[1],
        )[0]

    def replace(self, i: int, c: Char) -> None:
        self.categories[to_char(self.password[i])] -= 1
        self.categories[c] += 1

    def remove(self, i: int) -> None:
        self.categories[to_char(self.password[i])] -= 1
        self.length -= 1

    def shorten_most_used(self) -> None:
        self.steps += self.length - MAX_LENGTH
        self.length = MAX_LENGTH

    def shorten_repeats(self) -> None:
        while self.sequences and self.length > MAX_LENGTH:
            self.sequences.sort(key=lambda e: -((e[1] - e[0]) % 3))
            repeat = self.sequences.pop()
            c = to_char(self.password[repeat[0]])
            self.categories[c] -= 1
            self.length -= 1
            self.steps += 1
            if repeat[1] - repeat[0] > 3:
                self.sequences.append((repeat[0] + 1, repeat[1]))

    def lengthen(self) -> None:
        self.lengthen_sequence()
        while self.length < MIN_LENGTH:
            c = self.least_used_cat_char()
            self.categories[c] += 1
            self.steps += 1
            self.length += 1

    def lengthen_sequence(self) -> None:
        if self.sequences:
            _ = self.sequences.pop()
            c = self.least_used_cat_char()
            self.categories[c] += 1
            self.length += 1
            self.steps += 1

    def fix(self) -> None:
        self.fix_sequences()

        if self.categories[Char.UPPER] == 0:
            self.steps += 1
        if self.categories[Char.LOWER] == 0:
            self.steps += 1
        if self.categories[Char.DIGIT] == 0:
            self.steps += 1

    def fix_sequences(self) -> None:
        while self.sequences:
            s = self.sequences.pop()

            index = s[0] + 2
            c = to_char(self.password[index])
            self.categories[c] -= 1

            least = self.least_used_cat_char()
            self.categories[least] += 1

            self.steps += 1

            if index < s[1] - 3:
                self.sequences.append((index + 1, s[1]))


class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        return Solver(password).solve()


17000