Find the Fewest Edits Needed to Strengthen a Password
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Find the Fewest Edits Needed to Strengthen a Password
A password is strong only when all three conditions hold:
- Its length is from `6` through `20`, inclusive.
- It includes a lowercase letter, an uppercase letter, and a digit.
- It never contains three identical consecutive characters.
One edit inserts one character, deletes one character, or replaces one character with another. Return the minimum number of edits needed to make the given `password` strong. Return `0` if it already meets every rule.
### Function
`int strongPasswordChecker(string password)`
### Example 1
```text
Input: password = "aaaaAA1"
Output: 1
```
Replacing one of the middle lowercase `a`s gives `"aaBaAA1"`, which meets every rule.
### Example 2
```text
Input: password = "aaaaaaaaaaaaaaaaaaaaa"
Output: 7
```
The input has `21` lowercase `a`s. One deletion is necessary to reach the length limit. Six further replacements suffice, for example producing `"aaBaa1aaBaa1aaBaa1aa"`; fewer total edits cannot meet all the rules.
### Constraints
- `1 <= password.length <= 50`.
- Input characters are letters, digits, `'.'`, or `'!'`.
### Clarifications
The required character types are lowercase letters, uppercase letters, and digits; punctuation does not satisfy any of them. Edits may address more than one rule at once. Return only the edit count, not a particular strengthened password.
### What a Strong Answer Covers
- Lengths below, within, and above the permitted range.
- Missing character types and long runs of one character.
- Interactions among edits rather than independently adding costs for each rule.
- An optimality argument and resource bounds.
Overview: Practice finding the minimum insertions, deletions, and replacements required by precise password length, character-type, and repetition rules. Account for edits that address several requirements together.