Skip to main content

Strong Password Checker

Problem Description

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., "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 password with another character.

Examples

Example 1:

Input: password = "a"
Output: 5
Explanation: The password needs additional characters, an uppercase letter, and a digit to meet the criteria.

Example 2:

Input: password = "aA1"
Output: 3
Explanation: The password needs more characters to reach the minimum length of 6.

Constraints

  • 1 <= password.length <= 50
  • password consists of letters, digits, dot '.' or exclamation mark '!'.

Solution for Strong Password Checker

Approach

  • A strong password should contain at least one lowercase letter, one uppercase letter, and one number.
  • It should avoid having the same character repeated three times consecutively and be between 6 and 20 characters long.

The code achieves this by following these steps:

  1. Utilizes a “requirements” checklist to keep track of the first three criteria (initially unchecked).
  2. Maintains a record of character repetitions.
  3. Examines each character in the text:
    • If different from the previous character, checks off requirements if not met.
    • If the same as the previous character, counts consecutive repetitions.
  4. Sorts the repeated characters list by the number of repetitions.
  5. Adjusts the text:
    • For text longer than 20 characters, removes one repeated character in sequences of three or more.
    • For texts without such sequences, removes one character from the repeated character list.
    • Continues until the text is 20 characters or less.
  6. Calculates the number of characters needed to make the text at least 6 characters long (if it’s shorter).
  7. Totals all the changes made to meet the rules, providing the minimum number of changes required to create a strong password.

Code in Different Languages

Written by @Shreyash3087
class Solution {
public:
int strongPasswordChecker(string s) {
bitset<3> requirements{111};
list<int> repeats;
auto it = s.begin();
auto it2 = s.end();
while (it != s.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 != s.end() && *it == *it2)
++it;
if (distance(it2, it) != 2)
repeats.push_back(distance(it2, it));
if (it != s.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>(s.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;
}
};

Complexity Analysis

Time Complexity: O(N)O(N)

Reason: The code iterates through the input string once and performs various operations such as checking character types, counting repeated characters, and maintaining a list of repeats.

Space Complexity: O(N)O(N)

Reason: The space complexity is linear because the size of the repeats list is proportional to the length of the input

References


Authors:

Loading...