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
55
class Solution {
 public:
  int strongPasswordChecker(string s) {
    const int n = s.length();
    const int missing = getMissing(s);
    // # of replacements to deal with 3 repeating characters
    int replaces = 0;
    // # of seqs that can be substituted with 1 deletions, (3k)-seqs
    int oneSeq = 0;
    // # of seqs that can be substituted with 2 deletions, (3k + 1)-seqs
    int twoSeq = 0;

    for (int i = 2; i < n;)
      if (s[i] == s[i - 1] && s[i - 1] == s[i - 2]) {
        int length = 2;  // Length of repeating s
        while (i < n && s[i] == s[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& s) {
    int missing = 3;
    if (any_of(begin(s), end(s), [](char c) { return isupper(c); }))
      --missing;
    if (any_of(begin(s), end(s), [](char c) { return islower(c); }))
      --missing;
    if (any_of(begin(s), end(s), [](char c) { return isdigit(c); }))
      --missing;
    return missing;
  }
};

 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
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
  public int strongPasswordChecker(String s) {
    final int n = s.length();
    final char[] chars = s.toCharArray();
    final int missing = getMissing(chars);
    // # of replacements to deal with 3 repeating characters
    int replaces = 0;
    // # of seqs that can be substituted with 1 deletions, (3k)-seqs
    int oneSeq = 0;
    // # of seqs that can be substituted with 2 deletions, (3k + 1)-seqs
    int twoSeq = 0;

    for (int i = 2; i < n;)
      if (chars[i] == chars[i - 1] && chars[i - 1] == chars[i - 2]) {
        int length = 2; // Length of repeating chars
        while (i < n && chars[i] == chars[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 char[] chars) {
    int missing = 3;

    for (final char c : chars)
      if (Character.isUpperCase(c)) {
        --missing;
        break;
      }

    for (final char c : chars)
      if (Character.isLowerCase(c)) {
        --missing;
        break;
      }

    for (final char c : chars)
      if (Character.isDigit(c)) {
        --missing;
        break;
      }

    return missing;
  }
}