Strong Password Checker

Strong Password Checker is a classic greedy problem disguised as a string puzzle. The trick is to notice that the password has three independent problems — missing character types, long repeating runs, and a bad length — and that one well-placed edit can sometimes fix several at once.

The slow way first

You might try to search over edit sequences — insert here, replace there, delete elsewhere — looking for the shortest path to a strong password. That blows up fast: at every position you could do any of three operations, so the search space is exponential.

The question to ask: can I compute each requirement independently, then merge the answers cheaply? It turns out you can. The three problems — missing types, repeat runs, and length — each have a clean minimum cost, and greedy reasoning tells us how they overlap.

The idea: three costs, then combine greedily

Compute three numbers. Missing types: how many of {lowercase, uppercase, digit} are absent (0–3). Replacements: every run of L equal characters needs L // 3 replacements to break it. Length fixes: how far the length is from the 6–20 window — inserts if too short, deletes if too long.

The greedy insight is that these costs share work when the password is short or long. If you must insert characters anyway, each insert can also break a run and add a missing type.

The key case for our example is a short password (n < 6): the answer is simply the maximum of the three costs, because one inserted character can serve as a missing type and break a run simultaneously.

Walk through it

Step through the animation. First we scan all characters and find we have lowercase and a digit but no uppercase, so missing types = 1. Then we spot the run of three as, which costs 3 // 3 = 1 replacement. The length is 5, one short of 6, so we need 1 insert. Because n < 6, the answer is max(1, 1, 1) = 1 — a single uppercase letter dropped into the run fixes everything.

Pseudocode

missing = 3 minus (has lowercase) minus (has uppercase) minus (has digit)
 
replace = 0
for each maximal run of equal characters of length L:
    replace += L // 3            # breaking every 3rd char kills the run
 
if length < 6:
    return max(6 - length, missing, replace)   # inserts double as fixes
else if length <= 20:
    return max(missing, replace)                # replacements double as fixes
else:
    # delete down to 20 first, then count remaining replacements
    ...

The Python solution

def strong_password(s):
    n = len(s)
    missing = 3
    if any(c.islower() for c in s): missing -= 1
    if any(c.isupper() for c in s): missing -= 1
    if any(c.isdigit() for c in s): missing -= 1
 
    replace = 0
    i = 2
    while i < n:
        if s[i] == s[i-1] == s[i-2]:
            replace += (run_len // 3)
        i += 1
 
    if n < 6:
        return max(6 - n, missing, replace)
    # (n in 6..20: return max(missing, replace); n > 20 also deletes)

• missing starts at 3 and drops by one for each character type we actually find.
• The while loop walks runs of three-or-more equal characters; each run of length L contributes L // 3 replacements.
• For a short password (n < 6) the answer is max(6 - n, missing, replace) — every insert we are forced to add can also add a type and split a run, so no cost is paid twice.
• The commented branches handle the in-range and over-long cases; over-long passwords delete down to 20 first, since deletions can shorten runs and reduce the replacement count.

Complexity

We replace an exponential search with a single linear pass and a few max comparisons. The whole problem collapses once you treat the three requirements separately and notice where their fixes overlap.

When this pattern shows up

Practice