{x}
blog image

Strong Password Checker

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.

 

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 <= 50
  • password consists of letters, digits, dot '.' or exclamation mark '!'.

Solution Explanation for Strong Password Checker

This problem requires determining the minimum number of steps to transform a given password into a strong password. A strong password adheres to these rules:

  1. Length between 6 and 20 characters.
  2. Contains at least one lowercase letter, one uppercase letter, and one digit.
  3. No three consecutive repeating characters.

The solution employs a greedy approach, handling different scenarios based on password length:

1. Password Length Less Than 6:

  • The solution calculates the number of characters needed to reach a minimum length of 6 (6 - n).
  • It also determines the number of character types missing (3 - types).
  • The maximum of these two values represents the minimum steps needed.

2. Password Length Between 6 and 20:

  • The code first counts the number of repeating character sequences of length 3 or more. It iterates through the password, keeping track of consecutive repeating characters. When a different character is encountered, it adds the number of groups of 3 repeating characters to replace.
  • The number of missing character types (3 - types) is also calculated.
  • The maximum of these two values is returned as the minimum number of steps.

3. Password Length Greater Than 20:

This is the most complex case. The strategy is to reduce the password length to 20 while minimizing the changes required to meet the other criteria.

  • The number of characters to remove (remove = n - 20) is determined.

  • The code iterates and identifies groups of repeating characters, similar to the previous case, calculating replace. Crucially, it prioritizes removing characters from repeating sequences of length greater than or equal to 3 to optimize the number of replacements needed. It keeps track of whether removing characters from sequences of length 3, 4, or 5 would be more efficient.

  • A sequence of length 3 can be reduced to length 2 using one removal; length 4 can be reduced to length 2 using two removals (or 3 using 1 removal and 1 replacement), and length 5 can be reduced using three removals (or 4 using 2 removals and 1 replacement). The code tries to make efficient use of the removals.

  • Finally, the code calculates the total number of steps as the sum of characters to remove, plus the remaining replacements required, and the missing character types, taking the maximum of the last two.

Time Complexity Analysis:

The solution iterates through the password string once in each case. Therefore, the time complexity is O(n), where n is the length of the password.

Space Complexity Analysis:

The space complexity is O(1) because the solution uses only a constant amount of extra space to store variables regardless of the input size.

The provided code in Python, Java, and C++ implements this approach effectively. The core logic remains the same across all three languages; only the syntax and library functions differ slightly. Note that the C++ solution uses std::string methods for character manipulation. The Java solution uses helper functions for character type checking (lowercase, uppercase, digit). The Python solution leverages Python's built-in string methods for this purpose.