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.
DP? My first insight. if the password is 'aaaaa' we need to insert character to make its length longer than five also make it not contain three repeating characters.
1 <= password.length <= 50 password consists of letters, digits, dot '.' or exclamation mark '!'.
This question is too hard. Let me see the std's solution.
- length, when the length is less than 6, we need to add when the length is more than 20, we need to delete the characters.
- lack. When we lack a capital letter or number. We need to insert it.
- repeating. we can add to truncate the repeating letters or replace the letter. But we also know that replacing can also solve the probelm of II and III. Adding can solve the problem of I and III.
When the length < 6, the problem III can be easily solved by adding some letters. There is a situation that if there is a repeating letter, and its repeating length is 3m + 2, we need to delete it to (3m + 2). For Example, k = 9, we delet some letters to make its length to 3*2 + 2. And bbbbb-> bbabb; we can replace a letter to make it valid.
we need to let the steps be minimum. If k % 3 == 1,2; we can ignore it. The std's code is strange... we can v[i] -= v[i] % k;
oh i understand, because the over is limited. we can first delete number 1. Then 2...
But here, we delete the duplicated letters to 3m + 2, the characters more than 20's letter need to be deleted too. Thus, we can combine these two operations, first we store a value over that record the number of letters out of 20. And, if we also need to delete some repeating letters, we can reduce over, it means, in repeating we also delete some letters, over can be done with deleting repeated letters.
The std has a problem. When the over is out of used in the 3m + 2's way, we need to delete over instead of k.