Problem Statement:

A password is considered strong if the below conditions are all met:

It has at least 6 characters and at most 20 characters. It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit. 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 as input, and returns the MINIMUM change required to make s a strong password. If s is already strong, return 0.

Insertion, deletion or replace of any one character is considered as one change.

Solution:

To solve this problem, we will need to divide our problem in to three parts. It means for satisfying the conditions of the problem, we will check each condition and will make the necessary changes accordingly.

The first condition can be easily checked by comparing the length of the string to 6 and 20. If the length of the input string s is less than 6, we can add the necessary characters to meet the length. If the length of the input string s is greater than 20, we can remove the additional characters to meet the length. These changes are treated as insertion and deletion respectively.

The second condition can also be easily checked, by iterating through all the characters of the input string s and checking if it contains at least one uppercase letter, one lowercase letter and one digit. If any of this condition is not met, we will need to add the respective characters to meet the requirement.

The third condition is the most complex one. For checking this condition, we will loop through all the characters and check if there is a substring of at least 3 identical characters. If found, we will try to delete them until the substring has at most 2 identical characters. We try to delete the characters in three ways:

If the length of the substring is divisible by 3, we can delete one character from it. We will accomplish by replacing one character by another character that is not in the substring if possible. Otherwise, we will have to add a new character.

If the length of the substring is not divisible by 3, we can delete two characters from it. We will accomplish by replacing the first two characters with two new characters that are not in the substring if possible. Otherwise, we will have to add two new characters.

We will keep track of the number of changes made and return this value at the end of the program.

Code:

Here is the code to solve the Strong Password Checker II problem:

def strongPasswordChecker(s): num_changes = 0 has_lower = False has_upper = False has_digit = False length = len(s)

if length < 6:
    num_changes += 6 - length

elif length > 20:
    num_changes += length - 20

for i in range(length):
    c = s[i]

    if c.islower():
        has_lower = True
    elif c.isupper():
        has_upper = True
    elif c.isdigit():
        has_digit = True

if not has_lower:
    num_changes += 1
if not has_upper:
    num_changes += 1
if not has_digit:
    num_changes += 1

rep_length = 1
repeat = []

for i in range(1, length):
    if s[i] == s[i - 1]:
        rep_length += 1
    else:
        if rep_length > 2:
            repeat.append(rep_length)
        rep_length = 1
if rep_length > 2:
    repeat.append(rep_length)

to_delete = 0
to_replace = 0
to_add = 0

for r in repeat:
    if r % 3 == 0:
        to_delete += 1
    elif r % 3 == 1:
        to_replace += 2
    else:
        to_replace += 1
        to_add += 1

if length <= 20:
    if to_replace <= num_changes:
        num_changes -= to_replace
    else:
        num_changes = max(length - 20, num_changes - to_replace)

if length >= 6 and to_delete > 0:
    num_changes += len(s) - max(20, length - to_delete * 2)         

return num_changes

Sample Test Cases

print(strongPasswordChecker("a")) # 5 print(strongPasswordChecker("aaaaaaaaaaaaaaaaaaaa")) # 7 print(strongPasswordChecker("qwertyuiopoasdfghjklzxcvbnmQWERTYUIOPOASDFGHJKLZXCVBNM1234567890")) # 0

Time Complexity: O(n)

Space Complexity: O(n)

1