Algorithm
Problem Name: 420. Strong Password Checker
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.
Example 1:
Input: password = "a" Output: 5
Example 2:
Input: password = "aA1" Output: 3
Example 3:
Input: password = "1337C0d3" Output: 0
Constraints:
1 <= password.length <= 50passwordconsists of letters, digits, dot'.'or exclamation mark'!
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const strongPasswordChecker = function(s) {
let n = s.length,
toAdd = Math.max(0, 6 - n),
toDel = Math.max(n - 20, 0),
repeat = Array.from({ length: 3 }, _ => []),
lower = 1,
upper = 1,
digit = 1,
add = 0,
del = 0,
rep = 0,
k = 0;
for (let i = 0; i < = n; i++) {
if (s[i] != s[k]) {
let len = i - k;
if (len >= 3) repeat[len % 3].push(len);
k = i;
}
if (i == n) break;
if (/\d/.test(s[i])) digit = 0;
if (/[a-z]/.test(s[i])) lower = 0;
if (/[A-Z]/.test(s[i])) upper = 0;
}
repeat.map((arr, mod) => {
for (let len of arr) {
if (toAdd - add > 0) {
len -= 2;
add++;
}
if (toDel - del > 0) {
del += mod + 1;
len -= mod + 1;
}
rep += (len / 3) | 0;
}
});
toDel - del > 0
? (rep = Math.max(0, rep - Math.floor((toDel - del) / 3)))
: (rep += del - toDel);
return toDel + Math.max(digit + lower + upper, rep + toAdd);
};
Input
password = "a"
Output
5
#2 Code Example with Python Programming
Code -
Python Programming
class Solution(object):
def strongPasswordChecker(self, s):
"""
:type s: str
:rtype: int
"""
missing_type = 3
if any('a' <= c <= 'z' for c in s): missing_type -= 1
if any('A' <= c <= 'Z' for c in s): missing_type -= 1
if any(c.isdigit() for c in s): missing_type -= 1
change = 0
one = two = 0
p = 2
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]:
length += 1
p += 1
change += length // 3
if length % 3 == 0: one += 1
elif length % 3 == 1: two += 1
else:
p += 1
if len(s) < 6:
return max(missing_type, 6 - len(s))
elif len(s) <= 20:
return max(missing_type, change)
else:
delete = len(s) - 20
change -= min(delete, one)
change -= min(max(delete - one, 0), two * 2) // 2
change -= max(delete - one - 2 * two, 0) // 3
return delete + max(missing_type, change)
Input
password = "a"
Output
5
#3 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Text;
namespace LeetCode
{
public class _0420_StrongPasswordChecker
{
public int StrongPasswordChecker(string s)
{
if (string.IsNullOrEmpty(s)) return 6;
var length = s.Length;
var sb = new StringBuilder();
sb.Append(s[0]);
for (int i = 1; i < length; i++)
{
if (s[i] != s[i - 1])
sb.Append(' ');
sb.Append(s[i]);
}
bool hasDigit = false, hasLower = false, hasUpper = false;
int replacements = 0;
var replace = new int[3] { 0, 0, 0 };
var words = sb.ToString().Split();
foreach (var word in words)
{
var ch = word[0];
hasDigit = hasDigit || char.IsDigit(ch);
hasLower = hasLower || char.IsLower(ch);
hasUpper = hasUpper || char.IsUpper(ch);
replacements += word.Length / 3;
if (word.Length >= 3)
replace[word.Length % 3]++;
}
var deletions = Math.Max(0, length - 20);
var additions = Math.Max((hasDigit ? 0 : 1) + (hasLower ? 0 : 1) + (hasUpper ? 0 : 1), 6 - length);
var d = deletions;
replacements -= Math.Min(replace[0], d);
d = Math.Max(d - replace[0], 0);
replacements -= Math.Min(replace[1], d / 2);
d = Math.Max(d - replace[1] * 2, 0);
replacements -= d / 3;
return deletions + Math.Max(replacements, additions);
}
}
}
Input
password = "aA1"
Output
3