Formatted question description: https://leetcode.ca/all/420.html
420. Strong Password Checker
Level
Hard
Description
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.
Solution
Use a priority queue to store the lengths of repeating characters, where the elements are sorted according to the results of modulo 3 in ascending order. Loop over s, check whether a lowercase letter, an uppercase letter and a digit exists, and find repeating characters and add the lengths into the priority queue. Then deal with the string under cases where length is less than 6 and length is greater than 20, respectively.
class Solution {
public int strongPasswordChecker(String s) {
int length = s.length();
if (length == 0)
return 6;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num1 % 3 - num2 % 3;
}
});
int repeatingCount = 1;
int lowerCaseCount = 1, upperCaseCount = 1, digitCount = 1;
char c0 = s.charAt(0);
if (Character.isLowerCase(c0))
lowerCaseCount = 0;
else if (Character.isUpperCase(c0))
upperCaseCount = 0;
else if (Character.isDigit(c0))
digitCount = 0;
char prevC = c0;
for (int i = 1; i < length; i++) {
char c = s.charAt(i);
if (Character.isLowerCase(c))
lowerCaseCount = 0;
else if (Character.isUpperCase(c))
upperCaseCount = 0;
else if (Character.isDigit(c))
digitCount = 0;
if (c == prevC)
repeatingCount++;
else {
if (repeatingCount >= 3)
priorityQueue.offer(repeatingCount);
repeatingCount = 1;
}
prevC = c;
}
if (repeatingCount >= 3)
priorityQueue.offer(repeatingCount);
int typeCount = lowerCaseCount + upperCaseCount + digitCount;
int changes = 0;
if (length == 5) {
if (typeCount >= 2 || repeatingCount == 5)
return typeCount;
else
return 1;
} else if (length < 5)
return 6 - length;
while (!priorityQueue.isEmpty() && length > 20) {
int curRepeatingCount = priorityQueue.poll();
changes++;
length--;
curRepeatingCount--;
if (curRepeatingCount >= 3)
priorityQueue.offer(curRepeatingCount);
}
if (length > 20)
changes += length - 20 + typeCount;
else {
int curCount = 0;
while (!priorityQueue.isEmpty()) {
int curRepeatingCount = priorityQueue.poll();
curCount += curRepeatingCount / 3;
}
changes += Math.max(curCount, typeCount);
}
return changes;
}
}