In this Leetcode Strong Password Checker problem solution A password is considered strong if the below conditions are all met:
- It has at least 6 characters and at most 20 characters.
- 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., “…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met).
we have given a string password, return the minimum number of steps required to make password strong. if the 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 password with another character.
Problem solution in Python.
class Solution:
def strongPasswordChecker(self, password: str) -> int:
def type_(c):
if c.isdigit(): return 0
if c.isupper(): return 1
return 2
numTypes = len(set(type_(c) for c in password))
if len(password) <= 4: return (6 - len(password))
if len(password) == 5: return max(1, 3 - numTypes)
lengthOfSequences = [len(list(li)) for _, li in itertools.groupby(password)]
numReplace = sum(length // 3 for length in lengthOfSequences)
if len(password) <= 20: return max(3 - numTypes, numReplace)
numDelete = len(password) - 20
for i, length in enumerate(lengthOfSequences):
if length >= 3 and length % 3 == 0 and numReplace > 0 and numDelete >= 1:
lengthOfSequences[i] -= 1
numReplace -= 1
numDelete -= 1
for i, length in enumerate(lengthOfSequences):
if length >= 3 and length % 3 == 1 and numReplace > 0 and numDelete >= 2:
lengthOfSequences[i] -= 2
numReplace -= 1
numDeletes -= 2
numReplace -= min(numDelete // 3, sum(length // 3 for length in lengthOfSequences))
return len(password) - 20 + max(numReplace, 3 - numTypes)
Problem solution in Java.
class Solution {
public static int strongPasswordChecker(String s) {
int deletions = 0, finalCounter = 0, insertions = 0, repeating = 1, changesSum;
int replacements = 0, length = s.length();
boolean digit, lowerCase, upperCase;
digit = lowerCase = upperCase = false;
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < length; i++) {
if (i > 19)
deletions++;
if (Character.isLowerCase(s.charAt(i)))
lowerCase = true;
if (Character.isUpperCase(s.charAt(i)))
upperCase = true;
if (Character.isDigit(s.charAt(i)))
digit = true;
if (i > 0) {
if (s.charAt(i) == s.charAt(i - 1))
repeating++;
else {
if (repeating > 2)
arr.add(repeating);
repeating = 1;
}
}
}
if (repeating > 2)
arr.add(repeating);
if (digit)
insertions++;
if (upperCase)
insertions++;
if (lowerCase)
insertions++;
insertions = 3 - insertions;
if(deletions > 0 && arr.size() > 0)
arr = arrayReducer(arr, deletions);
changesSum =listSum(arr);
finalCounter = deletions + changesSum;
if(insertions > 0){
if(changesSum >= insertions)
insertions = 0;
else
insertions = insertions - changesSum;
}
if(s.length() < 6) {
if(insertions < 6- (s.length()))
insertions = insertions + (6 - s.length() - insertions);
if(insertions > changesSum)
insertions = insertions - changesSum;
}
finalCounter = finalCounter + insertions;
return finalCounter;
}
public static int listSum (ArrayList<Integer> arr){
int sum = 0;
for(int i = 0; i < arr.size(); i ++ )
sum = sum + (arr.get(i)/3);
return sum;
}
public static ArrayList arrayReducer(ArrayList<Integer> arr, int i) {
int mod;
int current, counter = 0, flag = arr.size() + 1;
while(i>0) {
mod = counter%3;
for(int x = 0; x <arr.size(); x++) {
if( flag == 0 )
return arr;
current = arr.get(x);
if (current % 3 == mod) {
if (i >= (mod + 1)) {
i = i - (mod + 1);
arr.set(x, current - (mod + 1));
} else{
flag--;
if (mod == 0)
return arr;
}
if (i == 0)
return arr;
}
if(i < (mod + 1))
if(mod == 0)
return arr;
}
counter++;
}
return arr;
}
}
Problem solution in C++.
class Solution {
public:
int strongPasswordChecker(string s) {
// For diversity requirement.
bool lower_case(false), upper_case(false), digit(false);
// For repeats.
std::vector<int> run_lengths;
char curr;
int run_length(0);
for (int i = 0; i < s.size(); ++i) {
// Do we need new characters.
if (s[i] >= 'a' && s[i] <= 'z') {
lower_case = true;
} else if (s[i] >= 'A' && s[i] <= 'Z') {
upper_case = true;
} else if (s[i] > '0' && s[i] <= '9') {
digit = true;
}
// Repeats.
if (i == 0) {
curr = s[0];
run_length = 1;
continue;
}
if (s[i] == curr) {
++run_length;
} else {
if (run_length >= 3) {
run_lengths.push_back(run_length);
}
curr = s[i];
run_length = 1;
}
}
if (run_length >= 3) {
run_lengths.push_back(run_length);
}
// Number of new characters needed.
int num_new(0);
if (!lower_case) {
++num_new;
}
if (!upper_case) {
++num_new;
}
if (!digit) {
++num_new;
}
// We can resolve some repeats if we need to insert or delete characters.
int num_edits(0);
if (s.size() < 6) {
int num_inserts = 6 - s.size();
// Some of the inserts can also satisfy num_new.
num_new -= min(num_new, num_inserts);
// Some of the inserts can break run lengths.
for (int i = 0; i < run_lengths.size(); ++i) {
int rl = run_lengths[i];
while (num_inserts > 0 && rl >= 3) {
--num_inserts;
++num_edits;
rl -= 2;
}
while (num_new > 0 && rl >= 3) {
--num_new;
++num_edits;
rl -= 2;
}
run_lengths[i] = rl;
}
num_edits += num_inserts;
} else if (s.size() > 20) {
int num_deletes = s.size() - 20;
// Some of the deletes can break run lengths at the same priority as substitutions.
for (int i = 0; i < run_lengths.size(); ++i) {
int rl = run_lengths[i];
while (num_new > 0 && rl >= 3) {
--num_new;
++num_edits;
rl -= 3;
}
if (rl >= 3 && num_deletes > 0 && rl % 3 == 0) {
--num_deletes;
++num_edits;
rl -= 1;
}
run_lengths[i] = rl;
}
// Use the remainder of our deletion budget by priority.
// This is given by number of deletes needed to break a repeat.
for (int i = 0; i < run_lengths.size(); ++i) {
int rl = run_lengths[i];
if (rl >= 3 && num_deletes >= 2 && rl % 3 == 1) {
num_deletes -= 2;
num_edits += 2;
rl -= 2;
}
run_lengths[i] = rl;
}
for (int i = 0; i < run_lengths.size(); ++i) {
int rl = run_lengths[i];
while (rl >= 3 && num_deletes >= 3 && rl % 3 == 2) {
num_deletes -= 3;
num_edits += 3;
rl -= 3;
}
run_lengths[i] = rl;
}
num_edits += num_deletes;
}
// All remaining repeats will now be broken by substitutions.
int num_replace(0);
for (int rl : run_lengths) {
num_replace += rl / 3;
}
num_edits += num_replace;
// Some num_new can be satisfied by above substitutions.
num_new -= min(num_new, num_replace);
num_edits += num_new;
return num_edits;
}
};