LeetCode 420: Strong Password Checker

Problem Restatement

We are given a string password.

Return the minimum number of steps needed to make it strong.

A strong password must satisfy all three rules:

In one step, we may:

1. Insert one character.
2. Delete one character.
3. Replace one character with another character.

The source constraints are 1 <= password.length <= 50, and the password consists of letters, digits, dot ".", or exclamation mark "!".

Input and Output

Example function shape:

def strongPasswordChecker(password: str) -> int:
    ...

Examples

Example 1:

password = "a"

The answer is:

5

The password has only one character, so it needs at least five insertions to reach length 6.

Example 2:

password = "aA1"

The answer is:

3

It already has lowercase, uppercase, and digit, but its length is only 3.

We need three insertions.

Example 3:

password = "1337C0d3"

The answer is:

0

It already satisfies all rules.

First Thought: Fix Each Rule Separately

There are three problems:

1. Length may be too short or too long.
2. Some character types may be missing.
3. There may be repeated runs like "aaa".

A simple but wrong approach is to fix them independently and add the costs.

That overcounts because one operation can fix more than one problem.

For example, replacing one character inside "aaa" can break the repetition and also add a missing uppercase letter.

So we need to combine the edits carefully.

Key Insight

There are three cases by length.

The repeated runs are the subtle part.

For a run of the same character with length L, such as:

"aaaaaa"

the number of replacements needed to break triples is:

L // 3

Examples:

When the password is too long, deletions are mandatory. Good deletions can also reduce the number of replacements needed for repeated runs.

The best deletion order depends on L % 3.

So for long passwords, we spend deletions on repeated runs in that order.

Algorithm

First compute:

n = len(password)

Then count missing character types:

missing = number of missing groups among lowercase, uppercase, digit

Next, scan the password and collect lengths of repeated runs of size at least 3.

For example:

"aaabbcccc"

has runs:

aaa -> 3
cccc -> 4

For every run length L, add:

L // 3

to the initial replacement count.

Then handle length cases.

If n < 6:

answer = max(missing, 6 - n)

Insertions can increase length and add missing character types.

If 6 <= n <= 20:

answer = max(missing, replacements)

Replacements can break repeated runs and add missing types.

If n > 20:

1. Let delete = n - 20.
2. Use deletions to reduce repeated-run replacements.
3. Return:

delete + max(missing, remaining_replacements)

Correctness

For short passwords, at least 6 - n insertions are required to reach length 6. Also, at least missing operations are needed to supply missing character types. Each insertion can add one missing type, so the minimum is the larger of those two values.

For valid-length passwords, length edits are unnecessary. Every run of length L needs L // 3 replacements to remove all triples. Missing character types also require operations. A replacement inside a repeated run can also create a missing character type, so the minimum is the larger of missing and the replacement count.

For long passwords, at least n - 20 deletions are mandatory. Deletions should be used first because they are required anyway, and some of them can reduce future replacement work. A run with length divisible by 3 loses one replacement after one deletion. A run with remainder 1 loses one replacement after two deletions. A run with remainder 2 loses one replacement after three deletions. Processing runs in this order maximizes replacement reduction per deletion.

After all required deletions are used, the remaining problem has valid length, so the remaining cost is the larger of missing character types and remaining replacements. Adding the mandatory deletions gives the minimum total operations.

Complexity

The input length is at most 50, but the algorithm is linear.

Implementation

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

        has_lower = any(ch.islower() for ch in password)
        has_upper = any(ch.isupper() for ch in password)
        has_digit = any(ch.isdigit() for ch in password)

        missing = 3 - int(has_lower) - int(has_upper) - int(has_digit)

        replacements = 0
        mod0 = 0
        mod1 = 0

        i = 0

        while i < n:
            j = i

            while j < n and password[j] == password[i]:
                j += 1

            length = j - i

            if length >= 3:
                replacements += length // 3

                if length % 3 == 0:
                    mod0 += 1
                elif length % 3 == 1:
                    mod1 += 1

            i = j

        if n < 6:
            return max(missing, 6 - n)

        if n <= 20:
            return max(missing, replacements)

        delete = n - 20
        remaining_delete = delete

        use = min(mod0, remaining_delete)
        replacements -= use
        remaining_delete -= use

        use = min(mod1, remaining_delete // 2)
        replacements -= use
        remaining_delete -= use * 2

        use = remaining_delete // 3
        replacements -= use

        return delete + max(missing, replacements)

Code Explanation

We first check which character types exist:

has_lower = any(ch.islower() for ch in password)
has_upper = any(ch.isupper() for ch in password)
has_digit = any(ch.isdigit() for ch in password)

Then:

missing = 3 - int(has_lower) - int(has_upper) - int(has_digit)

counts how many required character groups are absent.

Next we scan repeated runs:

while j < n and password[j] == password[i]:
    j += 1

For a run length length, the initial number of replacements is:

replacements += length // 3

We also count how many repeated runs have remainder 0 or 1 modulo 3:

if length % 3 == 0:
    mod0 += 1
elif length % 3 == 1:
    mod1 += 1

These counters guide deletion priority when the password is too long.

For short passwords:

return max(missing, 6 - n)

For normal-length passwords:

return max(missing, replacements)

For long passwords, deletions are mandatory:

delete = n - 20

First, use one deletion on as many length % 3 == 0 runs as possible:

use = min(mod0, remaining_delete)
replacements -= use
remaining_delete -= use

Then use two deletions on as many length % 3 == 1 runs as possible:

use = min(mod1, remaining_delete // 2)
replacements -= use
remaining_delete -= use * 2

Finally, any three deletions can reduce one replacement:

use = remaining_delete // 3
replacements -= use

The answer is:

return delete + max(missing, replacements)

Testing

def test_strong_password_checker():
    s = Solution()

    assert s.strongPasswordChecker("a") == 5
    assert s.strongPasswordChecker("aA1") == 3
    assert s.strongPasswordChecker("1337C0d3") == 0

    assert s.strongPasswordChecker("aaa") == 3
    assert s.strongPasswordChecker("aaaaaa") == 2
    assert s.strongPasswordChecker("ABABABABABABABABABAB1") == 2

    assert s.strongPasswordChecker("bbaaaaaaaaaaaaaaacccccc") == 8
    assert s.strongPasswordChecker("aaaaAAAAAA000000123456") == 5

    print("all tests passed")

Test Notes