Solution For Strong Password Checker
Problem Statement:
A password is considered strong if the below conditions are all met:
- It has at least 6 characters and at most 20 characters.
- It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
- It must NOT contain three repeating characters in a row (“…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met).
Write a function strongPasswordChecker(s), that takes a string s representing the password and returns the minimum number of steps required to make it strong. If s is already strong, return 0.
A step is an operation that changes any single character of s, or adds/deletes a character from s.
Solution:
The problem requires us to count the minimum number of changes needed to make the given password strong. The changes could be addition, deletion, or modification of a character. It also specifies certain constraints that need to be followed while creating a strong password.
Observations:
Before diving into the actual solution, let’s discuss some observations:
1. If the length of the password is less than 6, we can add characters to the password to make it strong.
2. If the length of the password is greater than 20, we can remove characters from the password to make it strong.
3. For the second condition, we can keep track of whether the password has lowercase, uppercase, and numeric characters and modify the password accordingly.
4. For the third condition, we can keep track of repeating characters and modify the password accordingly.
Step 1: Identify the password length and the missing character types
In order to identify the count of missing types of characters, we need to check whether the password has at least one lowercase letter, uppercase letter, and digit. If not, we can add characters of missing type to the password.
Step 2: Identify the count of repeating characters
To identify the count of repeating characters, we can use the greedy approach. We can start by finding all repeating characters of length three and replace them with the character of a different type. For example, if we have “aaa”, we can make it “aA1”. After the replacement, we need to re-calculate the count of repeating characters. We repeat this process until there are no repeating characters of length three or more.
Step 3: Handle the password length
If the length of the password is less than 6, we need to add characters to the password. If the length of the password is more than 20, we need to remove characters from the password. We can keep track of the required operations and the remaining changes to be done.
Step 4: Return the count of required operations
After the above three steps, we can return the count of required operations to make the password strong.
Code:
The code block below implements the above approach. The variable “missing_type” keeps track of the missing types of characters. The variable “repeating_chars” keeps track of the count of repeating characters. The variable “operations” keeps track of the count of operations required to make the password strong. The function “replace_repeat_chars” replaces the repeating characters with a character of different type.
“`
def strongPasswordChecker(password: str) -> int:
# Length
n = len(password)
# Missing Type
missing_type = 3
if any('a' <= password <= 'z' for x in password):
missing_type -= 1
if any('A' <= password <= 'Z' for x in password):
missing_type -= 1
if any(x.isdigit() for x in password):
missing_type -= 1
# Repeating Characters
repeating_chars = 0
i = 0
while i < n:
length = 1
while i + length < n and password[i+length] == password[i]:
length += 1
if length >= 3:
repeating_chars += length // 3
i += length
# Operation
operations = 0
if n < 6:
operations = max(operations, missing_type + max(0, 6 - (n + missing_type)))
elif n <= 20:
operations = max(operations, missing_type, repeating_chars)
else:
delete = n - 20
repeating_chars_removed = 0
# Remove repeating characters first
for length in range(1,3):
i = 0
while i < n and delete > 0:
if password[i:i+length] == password[i+length:i+2*length]:
delete -= 1
i += length
repeating_chars_removed += 1
i += 1
# Remove other characters to make length <= 20
delete -= len(set(password) - set(password[i:i+length] for i in range(2, n) if password[i] == password[i-1] == password[i-2]))
operations = max(operations, repeating_chars_removed + max(missing_type, repeating_chars - repeating_chars_removed) + ceil(max(0, delete) / 1.0 / 2))
return operations
“`
Complexity Analysis:
The time complexity of the above solution is O(n), where n is the length of the given password. The space complexity of the solution is O(1) as we are using constant extra space.
Test Cases:
The below table lists some of the test cases for the given problem:
| Test Case | Explanation |
| — | — |
| strongPasswordChecker(“me”) | The password length is 2. We can add characters to make it strong. |
| strongPasswordChecker(“bbbbb”) | All characters are repeating. We can replace them to make it strong. |
| strongPasswordChecker(“BBAABBAA111”) | The password is already strong. |
| strongPasswordChecker(“Aa11!”) | The password is already strong. |
| strongPasswordChecker(“AAb11!”) | The password has all types of characters but has repeating characters. We can replace them to make it strong. |
| strongPasswordChecker(“123456789123456789123”) | The password is too long. We can remove characters to make it strong. |
| strongPasswordChecker(“[email protected]&4”) | The password is strong. |
Conclusion:
The problem could be solved using a combination of observations and a greedy approach. We need to keep track of the missing types of characters, the count of repeating characters, and the required operations. The time complexity of the solution is O(n), and the space complexity is O(1).
Step by Step Implementation For Strong Password Checker
/*
A password is considered strong if below conditions are all met:
It has at least 6 characters and at most 20 characters.
It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
It must NOT contain three repeating characters in a row ("...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).
Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUM change required to make s a strong password. If s is already strong, return 0.
Insertion, deletion or replace of any one character are all considered as one change.
*/
public int strongPasswordChecker(String s) {
int changes = 0, a = 1, A = 1, d = 1;
char[] ca = s.toCharArray();
int[] counts = new int[3];
for (int i = 0; i < ca.length;) {
if (Character.isLowerCase(ca[i])) a = 0;
if (Character.isUpperCase(ca[i])) A = 0;
if (Character.isDigit(ca[i])) d = 0;
int j = i;
while (i < ca.length && ca[i] == ca[j]) i++;
counts[Math.min(2, i - j)]++;
changes += (i - j) / 3;
}
if (a + A + d > 0) changes += Math.max(0, 6 - (ca.length + a + A + d));
int needUpper = Math.max(0, 1 - A), needLower = Math.max(0, 1 - a), needDigit = Math.max(0, 1 - d);
changes -= Math.min(changes, needUpper + needLower + needDigit);
changes -= Math.min(Math.max(counts[0] - needUpper, 0), (changes - needUpper) / 2);
changes -= Math.min(Math.max(counts[1] - needLower, 0), (changes - needLower) / 2);
changes -= Math.min(Math.max(counts[2] - needDigit, 0), (changes - needDigit) / 2);
return changes;
}def check_strong_password(password): # 1. at least 8 characters if len(password) < 8: return False # 2. contains at least one digit if not any(i.isdigit() for i in password): return False # 3. contains at least one lowercase character if not any(i.islower() for i in password): return False # 4. contains at least one uppercase character if not any(i.isupper() for i in password): return False # 5. contains at least one special character # special characters are defined as any character that is not a letter or a digit if not any(not i.isalnum() for i in password): return False return True
// Given a string, return whether it represents a valid password. // A valid password is at least 6 characters long and contains // at least one uppercase letter, one lowercase letter, and one // digit. function isValidPassword(password) { // at least 6 characters long if (password.length < 6) { return false; } // at least one uppercase letter var hasUpperCase = false; for (var i = 0; i < password.length; i++) { if (password[i] >= 'A' && password[i] <= 'Z') { hasUpperCase = true; break; } } if (!hasUpperCase) { return false; } // at least one lowercase letter var hasLowerCase = false; for (var i = 0; i < password.length; i++) { if (password[i] >= 'a' && password[i] <= 'z') { hasLowerCase = true; break; } } if (!hasLowerCase) { return false; } // at least one digit var hasDigit = false; for (var i = 0; i < password.length; i++) { if (password[i] >= '0' && password[i] <= '9') { hasDigit = true; break; } } if (!hasDigit) { return false; } // all checks passed return true; }int strongPasswordChecker(string s)
{
int n = s.length();
// base case
if(n==0) return 6;
// initialize three flags
bool hasDigit = false, hasLower = false, hasUpper = false;
// initialize two variables to keep track of repeated characters
int repeatCount = 1, totalRepeat = 0;
// scan the string
for(int i=0; i0 && s[i]==s[i-1])
{
repeatCount++;
}
// if current char is different from the previous one
else
{
// update totalRepeat
totalRepeat += repeatCount/3;
// if repeatCount is larger than 2, we need to add 1 to the number of changes
if(repeatCount>=3)
{
// if repeatCount is divisible by 3, we need to subtract 1 from the number of changes
if(repeatCount%3==0) totalRepeat--;
}
// reset repeatCount
repeatCount = 1;
}
}
// update totalRepeat for the last group of repeated characters
totalRepeat += repeatCount/3;
if(repeatCount>=3)
{
if(repeatCount%3==0) totalRepeat--;
}
// if the string is less than 6 characters long, we need to add the difference to the number of changes
if(n<6) return max(totalRepeat, 6-n);
// if the string is longer than 20 characters, we need to subtract the difference from the number of changes
if(n>20) return max(totalRepeat, n-20);
// otherwise, the number of changes is equal to totalRepeat
return totalRepeat;
} using System;
public class Solution {
public int StrongPasswordChecker(string s) {
// TODO: Implement solution
}
}