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

class Solution:
    MINLEN = 6
    MAXLEN = 20
    MAXRUN = 2
    LOWER_LETTERS = set('abcdefghijklmnopqrstuvwxyz')
    UPPER_LETTERS = set(c.upper() for c in LOWER_LETTERS)
    DIGITS = set('0123456789')

    def strongPasswordChecker(self, password: str) -> int:
        return self.astar_search(
            start=password,
            goal=self.valid_password,
            successors=self.modified_passwords,
            heuristic=self.heuristic,
        )

    def heuristic(self, password: str) -> int:
        run_corrections = sum(len(run)//3 for i, run in self.runs(password))
        has_lower = any(c.islower() for c in password)
        has_upper = any(c.isupper() for c in password)
        has_digit = any(c.isdigit() for c in password)
        missing_char_corrections = (not has_lower) + (not has_upper) + (not has_digit)
        return max(
            len(password) - self.MAXLEN,
            self.MINLEN - len(password),
            missing_char_corrections,
            run_corrections,
        )

    def modified_passwords(self, password: str):
        lower_count = sum(c.islower() for c in password)
        upper_count = sum(c.isupper() for c in password)
        digit_count = sum(c.isdigit() for c in password)
        long_runs = [(i, run) for (i, run) in self.runs(password) if len(run) > self.MAXRUN]
        if len(password) < self.MINLEN:
            # Insert a char
            i = long_runs[0][0] + 2 if long_runs else 0
            surrounding = set(password[max(0, i-1):i+2])
            char = (
                min(self.LOWER_LETTERS - surrounding) if lower_count == 0 else
                min(self.UPPER_LETTERS - surrounding) if upper_count == 0 else
                min(self.DIGITS - surrounding)
            )
            yield password[:i] + char + password[i:]
        elif len(password) > self.MAXLEN:
            # Delete a char
            if long_runs:
                for i, _ in long_runs:
                    yield password[:i] + password[i+1:]
            else:
                i = next(
                    i
                    for i, c in enumerate(password)
                    if not (
                            c.islower() and lower_count == 1
                        or  c.isupper() and upper_count == 1
                        or  c.isdigit() and digit_count == 1
                    )
                )
                yield password[:i] + password[i+1:]
        else:
            # Replace a char
            i = long_runs[0][0] + 2 if long_runs else min(
                i
                for i, c in enumerate(password)
                if not (
                        c.islower() and lower_count == 1
                    or  c.isupper() and upper_count == 1
                    or  c.isdigit() and digit_count == 1
                )
            )
            surrounding = set(password[max(0, i-1):i+2])
            char = (
                min(self.LOWER_LETTERS - surrounding) if lower_count == 0 else
                min(self.UPPER_LETTERS - surrounding) if upper_count == 0 else
                min(self.DIGITS - surrounding)
            )
            yield password[:i] + char + password[i+1:]

    def valid_password(self, password: str) -> bool:
        return (
            self.MINLEN <= len(password) <= self.MAXLEN
            and any(c.isupper() for c in password)
            and any(c.islower() for c in password)
            and any(c.isdigit() for c in password)
            and not any(len(run) > self.MAXRUN for i, run in self.runs(password))
        )

    def runs(self, password: str):
        i = 0
        for char, group in itertools.groupby(password):
            run = ''.join(group)
            yield i, run
            i += len(run)

    def astar_search(self, start, goal, successors, heuristic) -> int:
        frontier = [(0, 0, start)]
        visited = set()
        while frontier:
            _, dist, node = heapq.heappop(frontier)
            if node in visited:
                continue
            visited.add(node)
            if goal(node):
                return dist
            for successor in successors(node):
                heapq.heappush(frontier, (dist+1+heuristic(successor), dist+1, successor))

17100