Checking for a strong password fails for a case it shouldn't

I am working through Leetcode problem 420. Strong Password Checker. This is the 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 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., "...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).

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 

Although it's kind of brute force, I have a simple logic that covers all 3 requirements:

class Solution: def strongPasswordChecker(self, s: str) -> int: lower_case = 'abcdefghijklmnopqrstuvwxyz' upper_case = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' digits = '1234567890' steps = 0 # Checks the length of the password if len(s) < 6: steps += 6-len(s) elif len(s) > 20: steps += len(s) - 20 # Checks if the password has a lowercase, uppercase and a digit for i in range(0, len(s)): if (s[i] not in lower_case) and (s[i] not in upper_case) and (s[i] not in digits): steps += 1 # Checks if the password has three repeating characters in a row for j in range(0, len(s)-2): if (s[j] == s[j+1]) and (s[j] == s[j+2]): steps += 1 return steps 

However, it fails on this test case:

Input: "aaaB1" Output: 2 Expected: 1 

I don't understand why it's only expecting 1 step. The password is shorter than 6 characters and it has 3 repeating characters one after another.

1 Answer

It requires only one step which resolves two problems:

"aaaB1" => "a9aaB1" ^ 

So your algorithm needs improvement as currently it looks only at the individual violations without considering that (some of) the steps needed to resolve one violation might also be reused to resolve another one.

For instance, when a string is longer than 20, you'll need to carefully decide which characters to delete. You would first delete characters from sections that have too many repeated characters,...etc. If there are no such series (any more), then those are the only steps to take. But there can be situations where after removing characters to reduce the string length to 20, you still have some repetitions to break, through replacements. And you have then to insert characters of a group that might not have been represented yet, ...etc.

You might not have to always literally perform those string manipulations, but at least there should be some bookkeeping of what has been resolved and what hasn't yet, giving preference to steps that resolve multiple issues at once.

Be aware that this problem is categorised as "Hard", so don't expect it to be straightforward.