The Strong Password Checker problem asks you to determine the minimum number of steps required to make a given password string s strong. A strong password is defined as one that satisfies all of the following rules:
In one step, you can take one of the following actions:
Your task is to compute the minimum number of steps needed to make the given password strong. Each step can be any of the three operations described above, and you may use them in any order or combination.
At first glance, the problem seems to require checking each rule separately and fixing them one by one. However, the challenge is to minimize the number of steps, especially when the password is too short or too long or contains many repeating characters.
A brute-force approach might try all possible combinations of insertions, deletions, and replacements, but this quickly becomes impractical for longer strings. Instead, we need to:
The key is to efficiently combine operations so that, for example, a deletion can also help reduce repeating characters, or an insertion can introduce a required character type.
missing_types).k // 3 replacements).missing_types and 6 - len(s).missing_types and total replacements needed for repeats.len(s) - 20 characters.deletions + max(missing_types, replacements_after_deletion).k % 3 == 0, then k % 3 == 1, etc.).This approach ensures each operation is used as efficiently as possible, often solving two problems at once (like reducing length and breaking up repeats).
Let's consider the password "aaaB1":
Step 1: missing_types = 0 (all types present).
Step 2: One sequence of "aaa" needs 1 replacement.
Step 3: Since length < 6, need 1 insertion.
Step 4: The insertion can be used to break the repeat ("aaXaaB1"), so only 1 step is needed.
Final answer: 1.
Now, for "aaaaaaaAAAAAA6666bbbbaaaaaa" (length 24):
Step 1: missing_types = 0.
Step 2: Calculate replacements for each sequence:
- "aaaaaaa" (7): 2
- "AAAAAA" (6): 2
- "6666" (4): 1
- "bbbb" (4): 1
- "aaaaaa" (6): 2
Total replacements: 8
Step 3: Need 4 deletions.
Step 4: Use deletions on the longest repeating sequences to reduce replacements needed.
After optimal deletions, let's say replacements drop to 6.
Final answer: 4 (deletions) + 6 (replacements) = 10.
The Strong Password Checker problem requires efficiently combining insertions, deletions, and replacements to satisfy three password strength rules. The key insight is to process missing character types and repeating characters together, using deletions and insertions to address multiple issues at once. By categorizing the string based on its length, and prioritizing operations that solve more than one problem, we can achieve an optimal O(n) solution that works for all cases.
class Solution:
def strongPasswordChecker(self, s: str) -> int:
missing_type = 3
if any('a' <= c <= 'z' for c in s):
missing_type -= 1
if any('A' <= c <= 'Z' for c in s):
missing_type -= 1
if any(c.isdigit() for c in s):
missing_type -= 1
n = len(s)
change = 0
one = two = 0
i = 2
repeats = []
while i < n:
if s[i] == s[i-1] == s[i-2]:
length = 2
while i < n and s[i] == s[i-1]:
length += 1
i += 1
repeats.append(length)
else:
i += 1
total_change = sum(l // 3 for l in repeats)
if n < 6:
return max(missing_type, 6 - n)
elif n <= 20:
return max(missing_type, total_change)
else:
delete = n - 20
left = delete
# Try to delete in a way that minimizes replacements
for k in range(1, 3):
for i in range(len(repeats)):
if left > 0 and repeats[i] >= 3 and repeats[i] % 3 == (k - 1):
need = min(left, repeats[i] - 2)
repeats[i] -= need
left -= need
total_change = sum(l // 3 for l in repeats)
return delete + max(missing_type, total_change)
class Solution {
public:
int strongPasswordChecker(string s) {
int n = s.size();
int missing = 3;
if (any_of(s.begin(), s.end(), ::islower)) missing--;
if (any_of(s.begin(), s.end(), ::isupper)) missing--;
if (any_of(s.begin(), s.end(), ::isdigit)) missing--;
vector<int> repeats;
for (int i = 2; i < n;) {
if (s[i] == s[i-1] && s[i-1] == s[i-2]) {
int j = i-2;
while (i < n && s[i] == s[j]) i++;
repeats.push_back(i - j);
} else {
i++;
}
}
int total_change = 0;
for (int l : repeats) total_change += l / 3;
if (n < 6) {
return max(missing, 6 - n);
} else if (n <= 20) {
return max(missing, total_change);
} else {
int del = n - 20, left = del;
for (int k = 1; k <= 2; ++k) {
for (int i = 0; i < repeats.size(); ++i) {
if (left > 0 && repeats[i] >= 3 && repeats[i] % 3 == k - 1) {
int need = min(left, repeats[i] - 2);
repeats[i] -= need;
left -= need;
}
}
}
total_change = 0;
for (int l : repeats) total_change += l / 3;
return del + max(missing, total_change);
}
}
};
class Solution {
public int strongPasswordChecker(String s) {
int n = s.length();
int missing = 3;
if (s.chars().anyMatch(Character::isLowerCase)) missing--;
if (s.chars().anyMatch(Character::isUpperCase)) missing--;
if (s.chars().anyMatch(Character::isDigit)) missing--;
List<Integer> repeats = new ArrayList<>();
for (int i = 2; i < n;) {
if (s.charAt(i) == s.charAt(i-1) && s.charAt(i-1) == s.charAt(i-2)) {
int j = i-2;
while (i < n && s.charAt(i) == s.charAt(j)) i++;
repeats.add(i - j);
} else {
i++;
}
}
int totalChange = 0;
for (int len : repeats) totalChange += len / 3;
if (n < 6) {
return Math.max(missing, 6 - n);
} else if (n <= 20) {
return Math.max(missing, totalChange);
} else {
int del = n - 20, left = del;
for (int k = 1; k <= 2; k++) {
for (int i = 0; i < repeats.size(); i++) {
if (left > 0 && repeats.get(i) >= 3 && repeats.get(i) % 3 == k - 1) {
int need = Math.min(left, repeats.get(i) - 2);
repeats.set(i, repeats.get(i) - need);
left -= need;
}
}
}
totalChange = 0;
for (int len : repeats) totalChange += len / 3;
return del + Math.max(missing, totalChange);
}
}
}
var strongPasswordChecker = function(s) {
let n = s.length;
let missing = 3;
if (/[a-z]/.test(s)) missing--;
if (/[A-Z]/.test(s)) missing--;
if (/\d/.test(s)) missing--;
let repeats = [];
let i = 2;
while (i < n) {
if (s[i] === s[i-1] && s[i-1] === s[i-2]) {
let j = i-2;
while (i < n && s[i] === s[j]) i++;
repeats.push(i - j);
} else {
i++;
}
}
let totalChange = repeats.reduce((sum, len) => sum + Math.floor(len / 3), 0);
if (n < 6) {
return Math.max(missing, 6 - n);
} else if (n <= 20) {
return Math.max(missing, totalChange);
} else {
let del = n - 20, left = del;
for (let k = 1; k <= 2; k++) {
for (let i = 0; i < repeats.length; i++) {
if (left > 0 && repeats[i] >= 3 && repeats[i] % 3 === k - 1) {
let need = Math.min(left, repeats[i] - 2);
repeats[i] -= need;
left -= need;
}
}
}
totalChange = repeats.reduce((sum, len) => sum + Math.floor(len / 3), 0);
return del + Math.max(missing, totalChange);
}
};