Make writing a habit together! This is my first day to participate in the “Gold Digging Day New Plan · April More text challenge”, click to see the details of the activity

Topic describes

420. Strong password checker

A password is considered strong if it meets all of the following conditions: contains at least six 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.

3

case The input The output
1 a 5
2 aA1 3
3 1337C0d3 0

Thought analysis

  • The difficulty of this problem is that you need to give the optimization steps. It is not only necessary to determine whether it meets the requirements of strong passwords, but also to give an optimization scheme for non-strong passwords.
  • As the problem explains, we can only add, delete, or modify one character at a time. In terms of password length we will distinguish between three cases

  • So we are also targeted at these three cases of operation

Through the small

  • There are only three ways to optimize —- add, modify, and delete 1 character at a time.

  • When the password length is less than 6, we want to optimize to a strong password format. One of the requirements for a strong password is that it must be within 6 to 20 characters in length. Then we don’t have to delete it.
  • So let’s see what we can do if we have continuous characters that are repeated. Because our current password is less than six characters long, it can be up to five consecutive characters the same,

The value contains five same characters

  • For consecutive characters in 5 cases we can update one of them to break 3 consecutive characters. But strong passwords also need to contain at least three type characters. After five consecutive occurrences of the same character, there are only two types of elements, so we need to perform one more addition to meet the requirements of a strong password

  • In addition to the new scheme after the update, we can also directly in the continuous character has been added to crack the continuity and ensure the length.

  • The optimization steps of both schemes are 2

The value contains four characters

  • Because the current large condition is that the password length does not exceed 6, the same character four. The maximum password length is 5, which means the maximum password type is 2. At this point, it is obvious whether to replace or add the same character.
  • Addition can not only solve the problem of continuity, but also solve the problem of category addition and length, while update cannot solve the problem of length, so we need to adopt the method of addition here

  • So we choose to add a new element at the median of the continuous position and we are done upgrading.

The value contains three characters

  • Same password 3 and 4 are the same. So what we’re going to do is we’re going to add them to the left and the right of the median.

The formula

  • Suppose we have a password of length N. The type of characters in the password is T
  • Why are these three cases of 2,1,0 consecutive characters not analyzed anymore? Because the continuous character is less than 3, we don’t need to care about it, just add it. That is to say, we optimize step 6-n, or 3-t, for no more than 3 consecutive characters. It all depends on which one is bigger. 6-n is for satisfying the length, and 3-t is for satisfying the type.
  • If the same character is 3, 6-n
  • If the same character is 4, 6-n
  • If the same character is 5, 6-n

Moderate length

  • Moderate length means that the length is within 6~20, so at this stage, it is obvious that the new addition is not suitable for our optimization strategy, because it is likely to exceed the length due to the new addition. And in cracking the problem of continuous characters we can use update or delete to crack. It is also obvious that deletion is not appropriate when sequential characters exceed 4. So overall in the continuous character of the problem or update more suitable

  • No matter how many characters are in a row, we just need to avoid three characters in a row. Then we only need to group three consecutive characters. We just have to replace one of each group. Suppose we have consecutive characters k1,k2,k3…. kx
  • So the operation that we need to update is the sum of k over 3

X = k 1 3 + k 2 3 + k 3 3 + . . . . + k x 3 X = \frac{k_{1}}{3}+\frac{k_{2}}{3}+\frac{k_{3}}{3}+…. +\frac{k_{x}}{3}
  • The other thing we need to remember is to keep three types, let’s say our character type is T, 3-t is the operation we need; So let’s take the maximum of X and 3 minus t

The length is too large

  • Because the length is too large, adding is obviously not appropriate here, so it is update and delete. The first reaction is to say yes. However, when we delete to a certain length, there will be continuous characters, so the update is necessary.
  • So for fixes do we update and delete, or delete and update.

  • After such a picture, I believe that smart you should also know which way to change. Let’s take a look at the explanation given on the official website. I think it is analytical and clear

AC

class Solution { public int strongPasswordChecker(String password) { int n = password.length(); int hasLower = 0, hasUpper = 0, hasDigit = 0; for (int i = 0; i < n; ++i) { char ch = password.charAt(i); if (Character.isLowerCase(ch)) { hasLower = 1; } else if (Character.isUpperCase(ch)) { hasUpper = 1; } else if (Character.isDigit(ch)) { hasDigit = 1; } } int categories = hasLower + hasUpper + hasDigit; if (n < 6) { return Math.max(6 - n, 3 - categories); } else if (n <= 20) { int replace = 0; int cnt = 0; char cur = '#'; for (int i = 0; i < n; ++i) { char ch = password.charAt(i); if (ch == cur) { ++cnt; } else { replace += cnt / 3; cnt = 1; cur = ch; } } replace += cnt / 3; return Math.max(replace, 3 - categories); } else {int replace = 0, remove = n-20; Int rm2 = 0; // k mod 3 = 1; int cnt = 0; char cur = '#'; for (int i = 0; i < n; ++i) { char ch = password.charAt(i); if (ch == cur) { ++cnt; } else {if (remove > 0 && CNT >= 3) {if (CNT % 3 == 0) {if (CNT % 3 == 0) { --replace; } else if (CNT % 3 == 1) {// if (CNT % 3 == 1); } replace += CNT / 3;} replace += CNT / 3; cnt = 1; cur = ch; } } if (remove > 0 && cnt >= 3) { if (cnt % 3 == 0) { --remove; --replace; } else if (cnt % 3 == 1) { ++rm2; } } replace += cnt / 3; Int use2 = math.min (math.min (replace, rm2), remove / 2); int use2 = math.min (replace, rm2), remove / 2); replace -= use2; remove -= use2 * 2; Int use3 = math.min (replace, remove / 3); int use3 = math.min (replace, remove / 3); replace -= use3; remove -= use3 * 3; return (n - 20) + Math.max(replace, 3 - categories); }}}Copy the code

conclusion

  • The difficulty of this problem is that we need to use logical mathematical thinking. Categorize the discussion, and do different strategies for each situation. Specific code can be implemented according to the train of thought

\