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

| Rule | Requirement |
|---|---|
| Length | At least `6` characters and at most `20` characters |
| Character types | At least one lowercase letter, one uppercase letter, and one digit |
| Repetition | No three same characters in a row |

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

| Item | Meaning |
|---|---|
| Input | A string `password` |
| Output | Minimum number of operations |
| Operations | Insert, delete, or replace one character |
| Strong length | `6 <= len(password) <= 20` |
| Required types | Lowercase, uppercase, digit |
| Forbidden pattern | Three equal characters consecutively |

Example function shape:

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

## Examples

Example 1:

```python
password = "a"
```

The answer is:

```python
5
```

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

Example 2:

```python
password = "aA1"
```

The answer is:

```python
3
```

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

We need three insertions.

Example 3:

```python
password = "1337C0d3"
```

The answer is:

```python
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.

| Case | Main issue |
|---|---|
| `n < 6` | Need insertions |
| `6 <= n <= 20` | Need replacements for missing types and repeated runs |
| `n > 20` | Need deletions first, then replacements |

The repeated runs are the subtle part.

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

```python
"aaaaaa"
```

the number of replacements needed to break triples is:

```python
L // 3
```

Examples:

| Run | Length | Replacements |
|---|---:|---:|
| `"aaa"` | 3 | 1 |
| `"aaaa"` | 4 | 1 |
| `"aaaaa"` | 5 | 1 |
| `"aaaaaa"` | 6 | 2 |

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

| Run length mod 3 | Deletions needed to reduce replacement count by 1 |
|---|---:|
| `L % 3 == 0` | 1 deletion |
| `L % 3 == 1` | 2 deletions |
| `L % 3 == 2` | 3 deletions |

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

## Algorithm

First compute:

```python
n = len(password)
```

Then count missing character types:

```python
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:

```python
"aaabbcccc"
```

has runs:

```python
aaa -> 3
cccc -> 4
```

For every run length `L`, add:

```python
L // 3
```

to the initial replacement count.

Then handle length cases.

If `n < 6`:

```python
answer = max(missing, 6 - n)
```

Insertions can increase length and add missing character types.

If `6 <= n <= 20`:

```python
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:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the password and repeated runs |
| Space | `O(1)` | Only counters are used |

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

## Implementation

```python
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:

```python
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:

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

counts how many required character groups are absent.

Next we scan repeated runs:

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

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

```python
replacements += length // 3
```

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

```python
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:

```python
return max(missing, 6 - n)
```

For normal-length passwords:

```python
return max(missing, replacements)
```

For long passwords, deletions are mandatory:

```python
delete = n - 20
```

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

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

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

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

Finally, any three deletions can reduce one replacement:

```python
use = remaining_delete // 3
replacements -= use
```

The answer is:

```python
return delete + max(missing, replacements)
```

## Testing

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

| Test | Why |
|---|---|
| `"a"` | Too short and missing types |
| `"aA1"` | Has types but too short |
| `"1337C0d3"` | Already strong |
| `"aaa"` | Short password with repetition |
| `"aaaaaa"` | Valid length but repeated run |
| Long password | Requires deletions |
| Long repeated runs | Checks deletion priority |
| Mixed repeated groups | Checks interaction between deletions and replacements |