Strong Password Checker - Leetcode Solution

Problem Statement: A password is considered strong if the 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 representing the password and returns the minimum number of steps required to make it strong. If s is already strong, return 0.

A step is an operation that changes any single character of s, or adds/deletes a character from s.

Solution: The problem requires us to count the minimum number of changes needed to make the given password strong. The changes could be addition, deletion, or modification of a character. It also specifies certain constraints that need to be followed while creating a strong password.

Observations: Before diving into the actual solution, let's discuss some observations:

1. If the length of the password is less than 6, we can add characters to the password to make it strong.
2. If the length of the password is greater than 20, we can remove characters from the password to make it strong.
3. For the second condition, we can keep track of whether the password has lowercase, uppercase, and numeric characters and modify the password accordingly.
4. For the third condition, we can keep track of repeating characters and modify the password accordingly.

Step 1: Identify the password length and the missing character types In order to identify the count of missing types of characters, we need to check whether the password has at least one lowercase letter, uppercase letter, and digit. If not, we can add characters of missing type to the password.

Step 2: Identify the count of repeating characters To identify the count of repeating characters, we can use the greedy approach. We can start by finding all repeating characters of length three and replace them with the character of a different type. For example, if we have "aaa", we can make it "aA1". After the replacement, we need to re-calculate the count of repeating characters. We repeat this process until there are no repeating characters of length three or more.

Step 3: Handle the password length If the length of the password is less than 6, we need to add characters to the password. If the length of the password is more than 20, we need to remove characters from the password. We can keep track of the required operations and the remaining changes to be done.

Step 4: Return the count of required operations After the above three steps, we can return the count of required operations to make the password strong.

Code: The code block below implements the above approach. The variable "missing_type" keeps track of the missing types of characters. The variable "repeating_chars" keeps track of the count of repeating characters. The variable "operations" keeps track of the count of operations required to make the password strong. The function "replace_repeat_chars" replaces the repeating characters with a character of different type.

def strongPasswordChecker(password: str) -> int:
    
    # Length
    n = len(password)

    # Missing Type
    missing_type = 3
    if any('a' <= password <= 'z' for x in password):
        missing_type -= 1
    if any('A' <= password <= 'Z' for x in password):
        missing_type -= 1
    if any(x.isdigit() for x in password):
        missing_type -= 1
        
    # Repeating Characters
    repeating_chars = 0
    i = 0
    while i < n:
        length = 1
        while i + length < n and password[i+length] == password[i]:
            length += 1
        if length >= 3:
            repeating_chars += length // 3
        i += length
    
    # Operation
    operations = 0
    if n < 6:
        operations = max(operations, missing_type + max(0, 6 - (n + missing_type)))
    elif n <= 20:
        operations = max(operations, missing_type, repeating_chars)
    else:
        delete = n - 20
        repeating_chars_removed = 0
        # Remove repeating characters first
        for length in range(1,3):
            i = 0
            while i < n and delete > 0:
                if password[i:i+length] == password[i+length:i+2*length]:
                    delete -= 1
                    i += length
                    repeating_chars_removed += 1
                i += 1
            
        # Remove other characters to make length <= 20
        delete -= len(set(password) - set(password[i:i+length] for i in range(2, n) if password[i] == password[i-1] == password[i-2]))
        operations = max(operations, repeating_chars_removed + max(missing_type, repeating_chars - repeating_chars_removed) + ceil(max(0, delete) / 1.0 / 2))

    return operations

Complexity Analysis: The time complexity of the above solution is O(n), where n is the length of the given password. The space complexity of the solution is O(1) as we are using constant extra space.

Test Cases: The below table lists some of the test cases for the given problem: | Test Case | Explanation | | --- | --- | | strongPasswordChecker("me") | The password length is 2. We can add characters to make it strong. | | strongPasswordChecker("bbbbb") | All characters are repeating. We can replace them to make it strong. | | strongPasswordChecker("BBAABBAA111") | The password is already strong. | | strongPasswordChecker("Aa11!") | The password is already strong. | | strongPasswordChecker("AAb11!") | The password has all types of characters but has repeating characters. We can replace them to make it strong. | | strongPasswordChecker("123456789123456789123") | The password is too long. We can remove characters to make it strong. | | strongPasswordChecker("Abcde1!2@3&4") | The password is strong. |

Conclusion: The problem could be solved using a combination of observations and a greedy approach. We need to keep track of the missing types of characters, the count of repeating characters, and the required operations. The time complexity of the solution is O(n), and the space complexity is O(1).

1