Strong Password Checker

Strong Password Checker

What is this problem about?

"Strong Password Checker" is widely considered one of the most complex string manipulation problems in technical interviews. You are given a password string and must find the minimum number of changes required to make it "strong." A strong password has:

1. Length between 6 and 20 characters.
2. At least one lowercase letter, one uppercase letter, and one digit.
3. No three consecutive identical characters (e.g., "aaa" is invalid). The allowed operations are insertion, deletion, and replacement of a character. The goal is to return the minimum number of such operations.

Why is this asked in interviews?

Companies like Microsoft, Google, and Meta ask this because it is an exhaustive test of edge-case handling and greedy optimization. It's not just about meeting the criteria; it's about doing so in the fewest steps possible. For example, a single replacement can fix a repeating sequence AND satisfy a missing character requirement (uppercase/lowercase/digit). The logic required to balance length constraints with repetition constraints is extremely subtle, making it a perfect filter for top-tier candidates.

Algorithmic pattern used

This problem follows a Greedy and Case-Based Logic pattern. The solution is usually divided into three scenarios based on length:

• If length < 6: You mainly use insertions.
• If length is 6-20: You mainly use replacements to fix repetitions and missing character types.
• If length > 20: You must use deletions first, specifically targeting repeating sequences that are most "efficient" to break (e.g., sequences of length 3n, then 3n+1, then 3n+2). A Priority Queue (Heap) can sometimes be used to manage the repeating sequences and decide which ones to shorten first during the deletion phase.

Example explanation (use your own example)

Take the password "aaaaaa" (length 6).

1. It has no uppercase and no digit. (2 missing types)
2. It has two "aaa" sequences ("aaa" and "aaa").
3. We can replace the 3rd 'a' with 'A' and the 6th 'a' with '1'. Result: "aaAaa1". This fixes both repeating sequences and adds the missing character types in just 2 operations. If we had "aaaaaaaaaaaaaaaaaaaaa" (21 characters), we would first delete one 'a' to get within the length limit, then proceed with replacements.

Common mistakes candidates make

The biggest mistake is not realizing that deletions should be prioritized for repeating sequences that are "one deletion away" from reducing the number of required replacements. Another common error is double-counting operations—for example, thinking you need an insertion and a replacement when one could solve both problems. Many candidates also fail to correctly implement the logic for passwords longer than 20 characters, which is the hardest part of the problem.

Interview preparation tip

Don't try to solve "Strong Password Checker" for the first time in an interview. It's a problem that requires deep study. Focus on the "length > 20" case and understand why deleting from a sequence of length 3, 6, 9... is more beneficial than deleting from a sequence of length 4, 7, 10... Draw out the state changes on paper to visualize how each operation affects the requirements.