Description
A password is considered strong if the below conditions are all met:
- It has at least
6characters and at most20characters. - It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
- It does not contain three repeating characters in a row (i.e.,
"Baaabb0"is weak, but"Baaba0"is strong).
Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.
In one step, you can:
- Insert one character to
password, - Delete one character from
password, or - Replace one character of
passwordwith another character.
Examples:
Example 1:
Input: password = "a"
Output: 5
Example 2:
Input: password = "aA1"
Output: 3
Example 3:
Input: password = "1337C0d3"
Output: 0Solution in Python
Approach:
To determine the minimum steps to make a password strong:
- Check Length Constraints:
- Passwords must have a length between 6 and 20 characters.
- If the length is less than 6, insertions are needed.
- If the length is greater than 20, deletions are needed.
- Check Character Requirements:
- Check if the password contains at least one lowercase letter, one uppercase letter, and one digit.
- Check Repeated Characters:
- Identify sequences of three or more repeated characters. Break these sequences using replacements or deletions.
- Calculate Total Steps:
- Combine the steps needed for length adjustments, character requirements, and removing/replacing repeating characters.
Python
class Solution:
def strongPasswordChecker(self, password: str) -> int:
# Initialize variables
n = len(password)
has_lower = False
has_upper = False
has_digit = False
change_count = 0
# Check for lowercase, uppercase, and digit presence
for char in password:
if char.islower():
has_lower = True
elif char.isupper():
has_upper = True
elif char.isdigit():
has_digit = True
# Count missing character types
missing_types = int(not has_lower) + int(not has_upper) + int(not has_digit)
# Step 1: Handle repeated characters
replace = 0
one_seq = two_seq = 0 # To track sequences of length % 3 == 1 or 2
i = 2 # Start checking from the third character
while i < n:
if password[i] == password[i - 1] == password[i - 2]: # Repeated character
length = 2 # Length of the current sequence
while i < n and password[i] == password[i - 1]:
length += 1
i += 1
replace += length // 3
if length % 3 == 0:
one_seq += 1
elif length % 3 == 1:
two_seq += 1
else:
i += 1
# Step 2: Handle length constraints
if n < 6:
# If password is too short, we need to add characters
return max(6 - n, missing_types)
elif n <= 20:
# If password length is valid, replacements handle missing types and repeats
return max(replace, missing_types)
else:
# If password is too long, deletions are required
delete_count = n - 20
# Optimize deletions to reduce replacements
replace -= min(delete_count, one_seq * 1) // 1
replace -= min(max(delete_count - one_seq, 0), two_seq * 2) // 2
replace -= max(delete_count - one_seq - 2 * two_seq, 0) // 3
return delete_count + max(replace, missing_types)Explanation of the Code:
- Character Type Check:
- The loop counts how many character types are missing (lowercase, uppercase, digits).
missing_typesholds the total number of character types that need to be added.
- Repeated Characters:
- Sequences of three or more repeated characters are identified.
- These sequences require replacements, but we prioritize breaking them based on their length modulo 3 to optimize deletions in the next step.
- Length Constraints:
- If the password is shorter than 6 characters, the required steps are the maximum of missing character types and the characters needed to reach length 6.
- If the password length is between 6 and 20, only replacements are needed.
- If the password is longer than 20, deletions are prioritized to reduce the length, and replacements handle the remaining issues.
- Optimize Steps:
- For overly long passwords, deletions are used strategically to minimize replacements for breaking repeated sequences.
Solution in C++
C++
class Solution {
public:
int strongPasswordChecker(string password) {
int n = password.length();
// Step 1: Check for the presence of lowercase, uppercase, and digit
bool hasLower = false, hasUpper = false, hasDigit = false;
for (char c : password) {
if (islower(c)) hasLower = true;
if (isupper(c)) hasUpper = true;
if (isdigit(c)) hasDigit = true;
}
// Count missing character types
int missingTypes = (!hasLower) + (!hasUpper) + (!hasDigit);
// Step 2: Count sequences of three or more repeating characters
int replaceCount = 0; // Number of replacements to break repeating sequences
int oneMod = 0, twoMod = 0; // Track lengths % 3 == 1 or 2
for (int i = 2; i < n; ++i) {
if (password[i] == password[i - 1] && password[i] == password[i - 2]) {
int length = 2; // Start with 3 repeating characters
while (i < n && password[i] == password[i - 1]) {
++length;
++i;
}
replaceCount += length / 3;
if (length % 3 == 0) ++oneMod;
else if (length % 3 == 1) ++twoMod;
}
}
// Step 3: Handle different password lengths
if (n < 6) {
// If password is too short, we need to add characters
return max(6 - n, missingTypes);
} else if (n <= 20) {
// If password length is valid, replacements handle repeating characters
return max(missingTypes, replaceCount);
} else {
// If password is too long, we need to delete characters
int deleteCount = n - 20;
// Optimize replacements by using deletions
replaceCount -= min(deleteCount, oneMod * 1) / 1;
replaceCount -= min(max(deleteCount - oneMod, 0), twoMod * 2) / 2;
replaceCount -= max(deleteCount - oneMod - 2 * twoMod, 0) / 3;
return deleteCount + max(missingTypes, replaceCount);
}
}
};Solution in Javascript
JavaScript
/**
* @param {string} password
* @return {number}
*/
var strongPasswordChecker = function(password) {
const n = password.length;
// Step 1: Check for the presence of lowercase, uppercase, and digit
let hasLower = false, hasUpper = false, hasDigit = false;
// Loop through the password to check for the required characters
for (let i = 0; i < n; i++) {
let c = password[i];
if (/[a-z]/.test(c)) hasLower = true;
if (/[A-Z]/.test(c)) hasUpper = true;
if (/\d/.test(c)) hasDigit = true;
}
// Count how many character types are missing
let missingTypes = 0;
if (!hasLower) missingTypes++;
if (!hasUpper) missingTypes++;
if (!hasDigit) missingTypes++;
// Step 2: Count sequences of three or more repeating characters
let replaceCount = 0; // Number of replacements to break repeating sequences
let oneMod = 0, twoMod = 0; // Track lengths % 3 == 1 or 2
let i = 2;
// Iterate through the password starting from the third character
while (i < n) {
if (password[i] === password[i - 1] && password[i] === password[i - 2]) {
let length = 2; // Start with length 2 because we know we already have 3 repeating characters
while (i < n && password[i] === password[i - 1]) {
length++;
i++;
}
replaceCount += Math.floor(length / 3); // For each sequence of length >= 3, add the number of replacements required
// Track how many sequences are of lengths % 3 == 0 or 1
if (length % 3 === 0) oneMod++;
else if (length % 3 === 1) twoMod++;
} else {
i++;
}
}
// Step 3: Handle different password lengths
if (n < 6) {
// If password is too short, we need to add characters
return Math.max(6 - n, missingTypes);
} else if (n <= 20) {
// If password length is valid, replacements handle repeating characters
return Math.max(missingTypes, replaceCount);
} else {
// If password is too long, we need to delete characters
let deleteCount = n - 20;
// Optimize replacements by using deletions
replaceCount -= Math.min(deleteCount, oneMod); // Use 1 deletion for each group % 3 == 0
replaceCount -= Math.floor(Math.min(Math.max(deleteCount - oneMod, 0), twoMod * 2) / 2); // Use 2 deletions for groups % 3 == 1
replaceCount -= Math.floor(Math.max(deleteCount - oneMod - 2 * twoMod, 0) / 3); // Use 3 deletions for groups % 3 == 2
return deleteCount + Math.max(missingTypes, replaceCount);
}
};
Solution in Java
Java
class Solution {
public int strongPasswordChecker(String password) {
int n = password.length();
// Step 1: Check for the presence of lowercase, uppercase, and digit
boolean hasLower = false, hasUpper = false, hasDigit = false;
for (char c : password.toCharArray()) {
if (Character.isLowerCase(c)) hasLower = true;
if (Character.isUpperCase(c)) hasUpper = true;
if (Character.isDigit(c)) hasDigit = true;
}
// Count missing character types
int missingTypes = (hasLower ? 0 : 1) + (hasUpper ? 0 : 1) + (hasDigit ? 0 : 1);
// Step 2: Count sequences of three or more repeating characters
int replaceCount = 0; // Number of replacements to break repeating sequences
int oneMod = 0, twoMod = 0; // Track lengths % 3 == 1 or 2
for (int i = 2; i < n; ++i) {
if (password.charAt(i) == password.charAt(i - 1) && password.charAt(i) == password.charAt(i - 2)) {
int length = 2; // Start with 3 repeating characters
while (i < n && password.charAt(i) == password.charAt(i - 1)) {
++length;
++i;
}
replaceCount += length / 3;
if (length % 3 == 0) oneMod++;
else if (length % 3 == 1) twoMod++;
}
}
// Step 3: Handle different password lengths
if (n < 6) {
// If password is too short, we need to add characters
return Math.max(6 - n, missingTypes);
} else if (n <= 20) {
// If password length is valid, replacements handle repeating characters
return Math.max(missingTypes, replaceCount);
} else {
// If password is too long, we need to delete characters
int deleteCount = n - 20;
// Optimize replacements by using deletions
replaceCount -= Math.min(deleteCount, oneMod); // Use 1 deletion for each group % 3 == 0
replaceCount -= Math.min(Math.max(deleteCount - oneMod, 0), twoMod * 2) / 2; // Use 2 deletions for groups % 3 == 1
replaceCount -= Math.max(deleteCount - oneMod - 2 * twoMod, 0) / 3; // Use 3 deletions for groups % 3 == 2
return deleteCount + Math.max(missingTypes, replaceCount);
}
}
}