Skip to content

420. Strong Password Checker 👎

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
 public:
  int strongPasswordChecker(string password) {
    const int n = password.length();
    const int missing = getMissing(password);
    // the number of replacements to deal with 3 repeating characters
    int replaces = 0;
    // the number of sequences that can be substituted with 1 deletions,
    // (3k)-seqs
    int oneSeq = 0;
    // the number of sequences that can be substituted with 2 deletions,
    // (3k + 1)-seqs
    int twoSeq = 0;

    for (int i = 2; i < n;)
      if (password[i] == password[i - 1] &&
          password[i - 1] == password[i - 2]) {
        int length = 2;  // the length of the repeating password
        while (i < n && password[i] == password[i - 1]) {
          ++length;
          ++i;
        }
        replaces += length / 3;  // 'aaaaaaa' -> 'aaxaaxa'
        if (length % 3 == 0)
          ++oneSeq;
        if (length % 3 == 1)
          ++twoSeq;
      } else {
        ++i;
      }

    if (n < 6)
      return max(6 - n, missing);
    if (n <= 20)
      return max(replaces, missing);

    const int deletes = n - 20;
    // Each replacement in (3k)-seqs can be substituted with 1 deletions.
    replaces -= min(oneSeq, deletes);
    // Each replacement in (3k + 1)-seqs can be substituted with 2 deletions.
    replaces -= min(max(deletes - oneSeq, 0), twoSeq * 2) / 2;
    // Each replacement in other seqs can be substituted with 3 deletions.
    replaces -= max(deletes - oneSeq - twoSeq * 2, 0) / 3;
    return deletes + max(replaces, missing);
  }

 private:
  int getMissing(const string& password) {
    return 3 -  //
           ranges::any_of(password, [](char c) { return isupper(c); }) -
           ranges::any_of(password, [](char c) { return islower(c); }) -
           ranges::any_of(password, [](char c) { return isdigit(c); });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
  public int strongPasswordChecker(String password) {
    final int n = password.length();
    final int missing = getMissing(password);
    // the number of replacements to deal with 3 repeating characters
    int replaces = 0;
    // the number of sequences that can be substituted with 1 deletions, (3k)-seqs
    int oneSeq = 0;
    // the number of sequences that can be substituted with 2 deletions, (3k + 1)-seqs
    int twoSeq = 0;

    for (int i = 2; i < n;)
      if (password.charAt(i) == password.charAt(i - 1) &&
          password.charAt(i - 1) == password.charAt(i - 2)) {
        int length = 2; // the length of the repeating password
        while (i < n && password.charAt(i) == password.charAt(i - 1)) {
          ++length;
          ++i;
        }
        replaces += length / 3; // 'aaaaaaa' -> 'aaxaaxa'
        if (length % 3 == 0)
          ++oneSeq;
        if (length % 3 == 1)
          ++twoSeq;
      } else {
        ++i;
      }

    if (n < 6)
      return Math.max(6 - n, missing);
    if (n <= 20)
      return Math.max(replaces, missing);

    final int deletes = n - 20;
    // Each replacement in (3k)-seqs can be substituted with 1 deletions.
    replaces -= Math.min(oneSeq, deletes);
    // Each replacement in (3k + 1)-seqs can be substituted with 2 deletions.
    replaces -= Math.min(Math.max(deletes - oneSeq, 0), twoSeq * 2) / 2;
    // Each replacement in other seqs can be substituted with 3 deletions.
    replaces -= Math.max(deletes - oneSeq - twoSeq * 2, 0) / 3;
    return deletes + Math.max(replaces, missing);
  }

  private int getMissing(final String password) {
    return 3 - //
        (password.chars().anyMatch(Character::isUpperCase) ? 1 : 0) -
        (password.chars().anyMatch(Character::isLowerCase) ? 1 : 0) -
        (password.chars().anyMatch(Character::isDigit) ? 1 : 0);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution:
  def strongPasswordChecker(self, password: str) -> int:
    n = len(password)
    missing = self._getMissing(password)
    # the number of replacements to deal with 3 repeating characters
    replaces = 0
    # the number of sequences that can be substituted with 1 deletions,
    # (3k)-seqs
    oneSeq = 0
    # the number of sequences that can be substituted with 2 deletions,
    # (3k + 1)-seqs
    twoSeq = 0

    i = 2
    while i < n:
      if password[i] == password[i - 1] and password[i - 1] == password[i - 2]:
        length = 2  # the length of the repeating password
        while i < n and password[i] == password[i - 1]:
          length += 1
          i += 1
        replaces += length // 3  # 'aaaaaaa' -> 'aaxaaxa'
        if length % 3 == 0:
          oneSeq += 1
        if length % 3 == 1:
          twoSeq += 1
      else:
        i += 1

    if n < 6:
      return max(6 - n, missing)
    if n <= 20:
      return max(replaces, missing)

    deletes = n - 20
    # Each replacement in (3k)-seqs can be substituted with 1 deletions.
    replaces -= min(oneSeq, deletes)
    # Each replacement in (3k + 1)-seqs can be substituted with 2 deletions.
    replaces -= min(max(deletes - oneSeq, 0), twoSeq * 2) // 2
    # Each replacement in other seqs can be substituted with 3 deletions.
    replaces -= max(deletes - oneSeq - twoSeq * 2, 0) // 3
    return deletes + max(replaces, missing)

  def _getMissing(self, password: str) -> int:
    return (3
            - any(c.isupper() for c in password)
            - any(c.islower() for c in password)
            - any(c.isdigit() for c in password))