Example 3:

Input: password = "1337C0d3"
Output: 0

Solution

Method 1 - Greedy / Simulation

Check character types: Count if the password contains at least one lowercase letter, one uppercase letter, and one digit.
Handle short passwords (n < 6): If the password is too short, the answer is the maximum of (6 - n) and the number of missing character types.
Handle valid length passwords (6 ≤ n ≤ 20): Count the number of replacements needed to fix sequences of three or more repeating characters. The answer is the maximum of the number of replacements and the number of missing character types.
Handle long passwords (n > 20): Calculate the number of deletions needed to reduce the length to 20. Use deletions to reduce the number of replacements needed for repeating characters. The answer is the number of deletions plus the maximum of the remaining replacements and the number of missing character types.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int strongPasswordChecker(string password) {\n        int types = countTypes(password);\n        int n = password.size();\n        if (n < 6) return max(6 - n, 3 - types);\n        if (n <= 20) {\n            int replace = 0, cnt = 0;\n            char prev = '~';\n            for (char& curr : password) {\n                if (curr == prev)\n                    ++cnt;\n                else {\n                    replace += cnt / 3;\n                    cnt = 1;\n                    prev = curr;\n                }\n            }\n            replace += cnt / 3;\n            return max(replace, 3 - types);\n        }\n        int replace = 0, remove = n - 20;\n        int remove2 = 0;\n        int cnt = 0;\n        char prev = '~';\n        for (char& curr : password) {\n            if (curr == prev)\n                ++cnt;\n            else {\n                if (remove > 0 && cnt >= 3) {\n                    if (cnt % 3 == 0) {\n                        --remove;\n                        --replace;\n                    } else if (cnt % 3 == 1)\n                        ++remove2;\n                }\n                replace += cnt / 3;\n                cnt = 1;\n                prev = curr;\n            }\n        }\n        if (remove > 0 && cnt >= 3) {\n            if (cnt % 3 == 0) {\n                --remove

Related Tags

Continue Practicing