# 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; } }