Make writing a habit together! This is the second day of my participation in the “Gold Digging Day New Plan · April More text challenge”. Click here for more details.
Title link: 420. Strong password checkers
Topic describes
A password is considered strong if it meets all of the following conditions:
- The value contains at least 6 to 20 characters.
- Contains at least one lowercase letter, one uppercase letter, and one number.
- The same character cannot appear three times in a row (e.g. “… aaa…” Is not allowed, but “… aa… a…” It can be a strong password if other conditions are met).
Given the string password, return the minimum number of steps needed to change the password to satisfy the strong password condition. If password is already a strong password, 0 is returned. In a modification operation, you can:
- Insert a character into the password,
- Delete a character from the password, or
- Replace a character in the password with another character.
Tip: 1<=password.length<=501 <=password.length<=50 passwordPasswordPassword Contains letters, digits, dots ‘.’ or exclamation marks! ‘
Example 1:
Input: password = "a" Output: 5Copy the codeExample 2:
Input: password = "aA1" Output: 3Copy the codeExample 3:
Enter: password = "1337C0d3" Output: 0Copy the codeThe main data structures and algorithms are not involved in the simulation.
Their thinking
According to the requirements in the question, we can divide the given string into three categories according to the length, namely: let the string length be n:
- N < 6 n < n < 6;
- 6<=n<=206 <=n<=206 <=n<=20;
- 20 < n20 < n20 < n.
- N < 6: It doesn’t make sense to delete or replace a string if n < 6; inserting a single character for the same number of operations will do the same (or better). Therefore, we only consider the operation of inserting characters. In order to ensure that both the string length and the character type meet the requirements of the question, the number of operations is the larger value of 6 − N and 3 – (character type), where 6-n represents the minimum number of operations to meet the requirements of the string length. (Character type) in 3 – (character type) indicates the number of character types that contain only uppercase and lowercase letters and digits. Therefore, 3 – (character type) indicates the number of missing character types, that is, the minimum operand that meets the character type.
- 6 <= n <= 20: it doesn’t make sense to delete or insert a string when 6 <= n <= 20. Replacing a character with 6 <= n <= 20 would have the same (or better) effect. For k consecutive identical characters, we can replace ⌊k3⌋\Big\lfloor \dfrac{k}{3} \Big\rfloor⌊3k⌋, so that there are no 3 consecutive identical characters (i.e. replace every 3 characters). We also need to ensure that the final string contains all three types of characters, so the number of substitution operations is the greater of (the sum of all ⌊k3⌋\Big\lfloor \dfrac{k}{3} \Big\rfloor⌊3k⌋) and (3−(character type)).
- 20 < n:When 20 < n when we insert the string is meaningless, can think so, if you insert a character, but in the end in order to meet the requirements of the title string length, also have to delete one character at a time, so in using the same number of operations, do not use the insert character operation can achieve the result of the same (or better). So there are still substitution and delete operations left. First we can consider deleting the string to case 2 (6 <= n <= 20) and then doing the substitution. So the question is, how to delete to minimize the number of operations in the final substitution? Deleting strings of consecutive length greater than or equal to 3 can reduce the number of final character substitution operations, but when faced with multiple strings of consecutive length greater than or equal to 3, how can we choose the best answer, for example,
aaa，bbbb，cccccAll three of these strings, for all three of these characters, they all need one substitution at the end of the substitution to make them fit the problem, but all three of these strings have different numbers of deletions,aaaI need to delete 1 character which is 1 delete operation,bbbbTwo deletions are required,cccccWith three deletions, we want to minimize the number of deletions, minimize the number of substitutions at the end, so when deleting characters, we first delete from all
Deletes 1 character from the same consecutive character group (thus reducing the number of substitution operations by 1), and then deletes all characters from the same consecutive character group
Delete two consecutive characters from the same character group, and the number of replacement operations is reduced by 1 for every three characters deleted. The final number of deletions is n-20, and the number of substitutions is (all
(sum), but several character replacement operations can be omitted by deleting character operations. Finally, the number of truly needed replacement operations needs to be larger than (3−(character type)) to ensure that the final string contains all three types of characters.
The subject summed up
This problem is easier to handle when the string length is less than 20. When the string length is more than 20, it is difficult to figure out how to correctly handle the replacement and delete operations.
Code section
class Solution {
public:
int strongPasswordChecker(string password) {
int n = password.length(a);// Check whether the password contains lowercase letters, uppercase letters, and numbers.
bool lower, upper, digit;
lower = upper = digit = false;
for(int i = 0; i < n; i++){
if(islower(password[i])) lower = true;
if(isupper(password[i])) upper = true;
if(isdigit(password[i])) digit = true;
}
// The number of types containing uppercase and lowercase letters and numbers
int sum = lower + upper + digit;
// If the length of n is less than 6, the operation of inserting characters is optimal and the number of inserting characters is the maximum
if(n < 6) return max(6 - n, 3 - sum);
// If length n <= 20, the substitution operation is optimal, and the number of substitutions is the sum of consecutive characters /3
else if(n <= 20) {int k = 0, num = 1;
for(int i = 1; i < n; i++){
if(password[i] == password[i - 1]) num++;
else{
k += num / 3;
num = 1; }}// Consider the case of consecutive characters at the end of the string
k += num / 3;
// Ensure that the character type meets the requirement
return max(k, 3 - sum);
}
// If n > 20
else{// n > 20
Replace and remove remove
int replace = 0, remove = n - 20;
Num % 3 == 1
int num = 1, rm2 = 0;
for(int i = 1; i < n; i++){
if(password[i] == password[i - 1]) num++;
else{
Num % 3 == 2; for each character removed, one replacement is removed
if(remove > 0 && num % 3= =0) {// num! = 0
remove--;
replace--;
}
Num % 3 == 2 num % 3 == 2
else if(num > 3 && num % 3= =1) rm2++;
Num % 3 == 2; num % 3 == 2
replace += num / 3;
num = 1; }}// Consider the case of consecutive characters at the end of the string
if(remove > 0 && num % 3= =0){
remove--;
replace--;
}
else if(num > 3 && num % 3= =1) rm2++;
replace += num / 3;
Num % 3 == 1; replace and remove are taken into account
int use2 = min({rm2, replace, remove / 2});
// Subtract 1 substitution for every 2 characters removed
replace -= use2;
remove -= use2 * 2;
// If num % 3 == 2, consider removing 1 substitution for every 3 characters
int use3 = min({replace, remove / 3});
Replace (num % 3 == 2); // Replace (num % 3 == 2)
replace -= use3;
remove -= use3 * 3;
// N-20 removals are required, but the number of replace can be reduced in the n-20 removals
// The number of replace must be the maximum number of missing character types to ensure that the character type meets the requirement
return n - 20 + max({replace, 3- sum}); }}};Copy the codeconclusion
Work silently, in order to be fruitful in tomorrow; Precipitation accumulation, is to accumulate in the future. Success is not achieved overnight, only dedication, power accumulation, in order to usher in the blossom.