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
6characters and at most
- 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
passwordis already strong, return
In one step, you can:
- Insert one character to
- Delete one character from
- Replace one character of
passwordwith 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.
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.