Strong Password Checker
Problem
A password must be 6–20 long, have at least one lower, upper, and digit, and contain no three repeating characters in a row. Return the minimum number of steps (insert/delete/replace) to make it strong.
password = "a"5def strong_password_checker(s):
n = len(s)
lower = upper = digit = 0
for ch in s:
if ch.islower(): lower = 1
elif ch.isupper(): upper = 1
elif ch.isdigit(): digit = 1
missing = 3 - (lower + upper + digit)
repls = 0
runs = [] # lengths of repeating runs >= 3
i = 2
while i < n:
if s[i] == s[i-1] == s[i-2]:
j = i - 2
while i < n and s[i] == s[j]: i += 1
runs.append(i - j)
else:
i += 1
repls_needed = sum(r // 3 for r in runs)
if n < 6:
return max(missing, 6 - n)
if n <= 20:
return max(missing, repls_needed)
# n > 20: deletions
excess = n - 20
remain = excess
for k in range(1, 3):
for idx, r in enumerate(runs):
if remain <= 0: break
if r % 3 == k - 1 and r >= 3:
d = min(remain, k)
runs[idx] -= d
remain -= d
for idx in range(len(runs)):
if remain <= 0: break
if runs[idx] >= 3:
d = (runs[idx] - 2) // 3 * 3
d = min(d, remain)
runs[idx] -= d
remain -= d
repls_needed = sum(r // 3 for r in runs)
return excess + max(missing, repls_needed)function strongPasswordChecker(s) {
const n = s.length;
let lower = 0, upper = 0, digit = 0;
for (const ch of s) {
if (/[a-z]/.test(ch)) lower = 1;
else if (/[A-Z]/.test(ch)) upper = 1;
else if (/[0-9]/.test(ch)) digit = 1;
}
const missing = 3 - (lower + upper + digit);
const runs = [];
for (let i = 2; i < n;) {
if (s[i] === s[i-1] && s[i] === s[i-2]) {
const j = i - 2;
while (i < n && s[i] === s[j]) i++;
runs.push(i - j);
} else i++;
}
if (n < 6) return Math.max(missing, 6 - n);
let repls = runs.reduce((a, r) => a + Math.floor(r / 3), 0);
if (n <= 20) return Math.max(missing, repls);
let excess = n - 20, remain = excess;
for (let k = 1; k < 3; k++) {
for (let idx = 0; idx < runs.length; idx++) {
if (remain <= 0) break;
if (runs[idx] % 3 === k - 1 && runs[idx] >= 3) {
const d = Math.min(remain, k);
runs[idx] -= d; remain -= d;
}
}
}
for (let idx = 0; idx < runs.length; idx++) {
if (remain <= 0) break;
if (runs[idx] >= 3) {
let d = Math.floor((runs[idx] - 2) / 3) * 3;
d = Math.min(d, remain);
runs[idx] -= d; remain -= d;
}
}
repls = runs.reduce((a, r) => a + Math.floor(r / 3), 0);
return excess + Math.max(missing, repls);
}class Solution {
public int strongPasswordChecker(String s) {
int n = s.length();
int lower = 0, upper = 0, digit = 0;
for (char c : s.toCharArray()) {
if (Character.isLowerCase(c)) lower = 1;
else if (Character.isUpperCase(c)) upper = 1;
else if (Character.isDigit(c)) digit = 1;
}
int missing = 3 - (lower + upper + digit);
List runs = new ArrayList<>();
for (int i = 2; i < n;) {
if (s.charAt(i) == s.charAt(i-1) && s.charAt(i) == s.charAt(i-2)) {
int j = i - 2;
while (i < n && s.charAt(i) == s.charAt(j)) i++;
runs.add(i - j);
} else i++;
}
if (n < 6) return Math.max(missing, 6 - n);
int repls = 0;
for (int r : runs) repls += r / 3;
if (n <= 20) return Math.max(missing, repls);
int excess = n - 20, remain = excess;
for (int k = 1; k < 3; k++) for (int idx = 0; idx < runs.size(); idx++) {
if (remain <= 0) break;
if (runs.get(idx) % 3 == k - 1 && runs.get(idx) >= 3) {
int d = Math.min(remain, k);
runs.set(idx, runs.get(idx) - d); remain -= d;
}
}
for (int idx = 0; idx < runs.size(); idx++) {
if (remain <= 0) break;
if (runs.get(idx) >= 3) {
int d = (runs.get(idx) - 2) / 3 * 3;
d = Math.min(d, remain);
runs.set(idx, runs.get(idx) - d); remain -= d;
}
}
repls = 0;
for (int r : runs) repls += r / 3;
return excess + Math.max(missing, repls);
}
} int strongPasswordChecker(string s) {
int n = s.size(), lower = 0, upper = 0, digit = 0;
for (char c : s) {
if (islower(c)) lower = 1;
else if (isupper(c)) upper = 1;
else if (isdigit(c)) digit = 1;
}
int missing = 3 - (lower + upper + digit);
vector runs;
for (int i = 2; i < n;) {
if (s[i] == s[i-1] && s[i] == s[i-2]) {
int j = i - 2;
while (i < n && s[i] == s[j]) i++;
runs.push_back(i - j);
} else i++;
}
if (n < 6) return max(missing, 6 - n);
int repls = 0;
for (int r : runs) repls += r / 3;
if (n <= 20) return max(missing, repls);
int excess = n - 20, remain = excess;
for (int k = 1; k < 3; k++) for (int idx = 0; idx < (int)runs.size(); idx++) {
if (remain <= 0) break;
if (runs[idx] % 3 == k - 1 && runs[idx] >= 3) {
int d = min(remain, k);
runs[idx] -= d; remain -= d;
}
}
for (int idx = 0; idx < (int)runs.size(); idx++) {
if (remain <= 0) break;
if (runs[idx] >= 3) {
int d = (runs[idx] - 2) / 3 * 3;
d = min(d, remain);
runs[idx] -= d; remain -= d;
}
}
repls = 0;
for (int r : runs) repls += r / 3;
return excess + max(missing, repls);
} Explanation
A strong password must be 6–20 characters, include a lowercase, uppercase, and digit, and have no run of three identical characters. We count the minimum number of insert, delete, or replace steps using a greedy case analysis on the password's length.
First we tally how many character classes are missing (out of lower/upper/digit) and find every repeating run of length 3 or more. A run of length r needs r // 3 replacements to break up all its triples.
If the password is too short (n < 6), the answer is max(missing, 6 - n) — the inserts we add can double as the missing classes. If the length is fine (6..20), the answer is max(missing, replacements), since each replacement can also fix a missing class.
If it is too long (n > 20), we must delete excess = n - 20 characters. We spend those deletions cleverly on the runs first — runs with length r % 3 == 0 need just 1 deletion to remove a replacement, then % 3 == 1 runs, and so on — to minimize leftover replacements. The final cost is excess + max(missing, remaining_replacements).
Example: password = "a" has length 1, so it is too short. We need 5 more characters to reach length 6, and those insertions also cover the missing classes, giving 5.