Last updated on January 18th, 2025 at 09:45 pm
Here, we see a Strong Password Checker LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
String
Level of Question
Hard
Strong Password Checker LeetCode Solution
Table of Contents
1. Problem Statement
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
2. Coding Pattern Used in Solution
The coding pattern used in this problem is Greedy Algorithm. The solution involves making optimal local decisions (e.g., reducing repeated characters, handling length constraints, and fulfilling character requirements) to achieve the global goal of transforming the password into a strong password.
3. Code Implementation in Different Languages
3.1 Strong Password Checker C++
class Solution {
public:
int strongPasswordChecker(string password) {
bitset<3> requirements{111};
list<int> repeats;
auto it = password.begin();
auto it2 = password.end();
while (it != password.end()) {
if (*it != *it2) {
if (requirements.test(0) && islower(*it))
requirements.reset(0);
if (requirements.test(1) && isupper(*it))
requirements.reset(1);
if (requirements.test(2) && isdigit(*it))
requirements.reset(2);
} else {
while (it != password.end() && *it == *it2)
++it;
if (distance(it2, it) != 2)
repeats.push_back(distance(it2, it));
if (it != password.end())
continue;
else
break;
}
it2 = it;
++it;
}
repeats.sort([](const int &lhs, const int &rhs) { return (lhs % 3) < (rhs % 3); });
int ans{0}, len{static_cast<int>(password.size())};
while (len > 20) {
if (!repeats.empty()) {
if (repeats.front() == 3) {
repeats.pop_front();
}
else {
--repeats.front();
repeats.sort([](const int &lhs, const int &rhs) { return (lhs % 3) < (rhs % 3); });
}
++ans;
--len;
}
else {
ans += len - 20;
len = 20;
}
}
int rep_ins{0};
while (!repeats.empty()) {
rep_ins += repeats.front() / 3;
repeats.pop_front();
}
if ((len + rep_ins) < 6) {
rep_ins += 6 - len - rep_ins;
}
ans += max(static_cast<int>(requirements.count()), rep_ins);
return ans;
}
};
3.2 Strong Password Checker Java
class Solution {
public int strongPasswordChecker(String password) {
int res = 0, a = 1, A = 1, d = 1;
char[] carr = password.toCharArray();
int[] arr = new int[carr.length];
for (int i = 0; i < arr.length;) {
if (Character.isLowerCase(carr[i])) a = 0;
if (Character.isUpperCase(carr[i])) A = 0;
if (Character.isDigit(carr[i])) d = 0;
int j = i;
while (i < carr.length && carr[i] == carr[j]) i++;
arr[j] = i - j;
}
int total_missing = (a + A + d);
if (arr.length < 6) {
res += total_missing + Math.max(0, 6 - (arr.length + total_missing));
} else {
int over_len = Math.max(arr.length - 20, 0), left_over = 0;
res += over_len;
for (int k = 1; k < 3; k++) {
for (int i = 0; i < arr.length && over_len > 0; i++) {
if (arr[i] < 3 || arr[i] % 3 != (k - 1)) continue;
arr[i] -= Math.min(over_len, k);
over_len -= k;
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= 3 && over_len > 0) {
int need = arr[i] - 2;
arr[i] -= over_len;
over_len -= need;
}
if (arr[i] >= 3) left_over += arr[i] / 3;
}
res += Math.max(total_missing, left_over);
}
return res;
}
}
3.3 Strong Password Checker JavaScript
var strongPasswordChecker = function (password) {
let numc = 1;
let upc = 1;
let loc = 1;
let cc = 0;
let cc2 = 0;
if (/[0-9]/.test(password) === true) {
numc = 0;
}
if (/[a-z]/.test(password) === true) {
loc = 0;
}
if (/[A-Z]/.test(password) === true) {
upc = 0;
}
for (let i = 0; i < password.length; i++) {
if (
password[i] === password[i + 1] &&
password[i + 1] === password[i + 2]
) {
i += 2;
cc += 1;
}
}
if (password.length < 6) {
return Math.max(loc + upc + numc, 6 - password.length);
} else if (password.length <= 20) {
return Math.max(loc + upc + numc, cc);
} else if (password.length > 20) {
password = password.split("");
let y = password.length - 20;
let x = password.length - 20;
let count = 1;
let a = [];
let b = [];
for (let i = 0; i < password.length; i++) {
if (password[i] === password[i + 1]) {
count += 1;
} else {
a.push(count);
b.push(count);
count = 1;
}
}
let i = 0;
while (i < 60 && x > 0) {
for (let i = 0; i < b.length && x > 0; i++) {
if (b[i] % 3 === 0 && b[i] >= 3) {
b[i] = b[i] - 1;
x = x - 1;
}
}
for (let i = 0; i < b.length && x > 0; i++) {
if (b[i] % 3 === 1 && b[i] >= 3) {
b[i] = b[i] - 1;
x = x - 1;
}
}
for (let i = 0; i < b.length && x > 0; i++) {
if (b[i] % 3 === 2 && b[i] >= 3) {
b[i] = b[i] - 1;
x = x - 1;
}
}
i++;
}
for (let i = 0; i < b.length; i++) {
for (let j = i + 1; j < b.length; j++) {
if (
b[i] >= 3 &&
b[j] >= 3 &&
b[i] % 3 === 0 &&
b[j] % 3 === 0 &&
b[i] !== a[i] &&
b[j] !== a[j]
) {
b[i] -= 1;
b[j] += 1;
} else if (
b[i] >= 3 &&
b[j] >= 3 &&
b[i] % 3 === 0 &&
b[j] % 3 === 1 &&
b[i] !== a[i] &&
b[j] !== a[j]
) {
b[i] -= 1;
b[j] += 1;
} else if (
b[i] >= 3 &&
b[j] >= 3 &&
b[i] % 3 === 1 &&
b[j] % 3 === 0 &&
b[i] !== a[i] &&
b[j] !== a[j]
) {
b[j] -= 1;
b[i] += 1;
}
}
}
cc2 = 0;
for (let i = 0; i < b.length; i++) {
if (b[i] >= 3) {
b[i] -= 3;
cc2 += 1;
i--;
}
}
return Math.max(loc + upc + numc, cc2) + y;
}
};
3.4 Strong Password Checker Python
class Solution(object):
def strongPasswordChecker(self, password):
missing_type = 3
if any('a' <= c <= 'z' for c in password): missing_type -= 1
if any('A' <= c <= 'Z' for c in password): missing_type -= 1
if any(c.isdigit() for c in password): missing_type -= 1
change = 0
one = two = 0
p = 2
while p < len(password):
if password[p] == password[p-1] == password[p-2]:
length = 2
while p < len(password) and password[p] == password[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(password) < 6:
return max(missing_type, 6 - len(password))
elif len(password) <= 20:
return max(missing_type, change)
else:
delete = len(password) - 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)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n log k) | O(n) |
| Java | O(n) | O(n) |
| JavaScript | O(n log k) | O(n) |
| Python | O(n) | O(n) |
where k is the number of repeated sequences.