##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/420.html

Hard

## Description

A password is considered strong if below conditions are all met:

1. It has at least 6 characters and at most 20 characters.
2. It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
3. 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 {
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;
}
}

• class Solution:
def countTypes(s):
a = b = c = 0
for ch in s:
if ch.islower():
a = 1
elif ch.isupper():
b = 1
elif ch.isdigit():
c = 1
return a + b + c

if n < 6:
return max(6 - n, 3 - types)
if n <= 20:
replace = cnt = 0
prev = '~'
if curr == prev:
cnt += 1
else:
replace += cnt // 3
cnt = 1
prev = curr
replace += cnt // 3
return max(replace, 3 - types)
replace = cnt = 0
remove, remove2 = n - 20, 0
prev = '~'
if curr == prev:
cnt += 1
else:
if remove > 0 and cnt >= 3:
if cnt % 3 == 0:
remove -= 1
replace -= 1
elif cnt % 3 == 1:
remove2 += 1
replace += cnt // 3
cnt = 1
prev = curr
if remove > 0 and cnt >= 3:
if cnt % 3 == 0:
remove -= 1
replace -= 1
elif cnt % 3 == 1:
remove2 += 1
replace += cnt // 3
use2 = min(replace, remove2, remove // 2)
replace -= use2
remove -= use2 * 2

use3 = min(replace, remove // 3)
replace -= use3
remove -= use3 * 3
return n - 20 + max(replace, 3 - types)

############

class Solution(object):
"""
:type s: str
:rtype: int
"""
complexBal = 3
if any(c in string.lowercase for c in s):
complexBal -= 1
if any(c in string.uppercase for c in s):
complexBal -= 1
if any(c.isdigit() for c in s):
complexBal -= 1

one = 0
two = 0
p = 2
replace = 0
while p < len(s):
if s[p] == s[p - 1] == s[p - 2]:
length = 2
while p < len(s) and s[p] == s[p - 1]:
p += 1
length += 1
replace += length / 3
if length % 3 == 0:
one += 1
if length % 3 == 1:
two += 1
else:
p += 1

if len(s) < 6:
return max(complexBal, 6 - len(s))
elif len(s) <= 20:
return max(complexBal, replace)
else:
redundant = len(s) - 20
replace -= min(redundant, one)
replace -= min(max(redundant - one, 0), two * 2) / 2
replace -= max(redundant - one - two * 2, 0) / 3
return redundant + max(complexBal, replace)


• class Solution {
public:
if (n < 6) return max(6 - n, 3 - types);
if (n <= 20) {
int replace = 0, cnt = 0;
char prev = '~';
for (char& curr : password) {
if (curr == prev)
++cnt;
else {
replace += cnt / 3;
cnt = 1;
prev = curr;
}
}
replace += cnt / 3;
return max(replace, 3 - types);
}
int replace = 0, remove = n - 20;
int remove2 = 0;
int cnt = 0;
char prev = '~';
for (char& curr : password) {
if (curr == prev)
++cnt;
else {
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
--remove;
--replace;
} else if (cnt % 3 == 1)
++remove2;
}
replace += cnt / 3;
cnt = 1;
prev = curr;
}
}
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
--remove;
--replace;
} else if (cnt % 3 == 1)
++remove2;
}
replace += cnt / 3;

int use2 = min(min(replace, remove2), remove / 2);
replace -= use2;
remove -= use2 * 2;

int use3 = min(replace, remove / 3);
replace -= use3;
remove -= use3 * 3;
return (n - 20) + max(replace, 3 - types);
}

int countTypes(string& s) {
int a = 0, b = 0, c = 0;
for (char& ch : s) {
if (islower(ch))
a = 1;
else if (isupper(ch))
b = 1;
else if (isdigit(ch))
c = 1;
}
return a + b + c;
}
};