How hard is LeetCode 420. Strong Password Checker?

LeetCode 420. Strong Password Checker is rated Hard on LeetCode.

What topics does LeetCode 420. Strong Password Checker cover?

LeetCode 420. Strong Password Checker is tagged Greedy, String and Heap (Priority Queue) on LeetCode.

Strong Password Checker — LeetCode 420 Python Solution

HardGreedyStringHeap (Priority Queue)

Problem: #420
Pattern: Heap / Priority Queue
Reading time: 10 min
Source: leetcode.com

The problem

A password is considered strong if the below conditions are all met: It has at least 6 characters and at most 20 characters. It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.

Example

Input: password = "a"
Output: 5

Python solution

Python

class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        def countTypes(s):
            a = b = c = 0
            for ch in s:
                if ch.islower():
                    a = 1
                elif ch.isupper():
                    b = 1
                elif ch.isdigit():
                    c = 1
            return a + b + c

        types = countTypes(password)
        n = len(password)
        if n < 6:
            return max(6 - n, 3 - types)
        if n <= 20:
            replace = cnt = 0
            prev = '~'
            for curr in password:
                if curr == prev:
                    cnt += 1
                else:
                    replace += cnt // 3
                    cnt = 1
                    prev = curr
            replace += cnt // 3
            return max(replace, 3 - types)
        replace = cnt = 0
        remove, remove2 = n - 20, 0
        prev = '~'
        for curr in password:
            if curr == prev:
                cnt += 1
            else:
                if remove > 0 and cnt >= 3:
                    if cnt % 3 == 0:
                        remove -= 1
                        replace -= 1
                    elif cnt % 3 == 1:
                        remove2 += 1
                replace += cnt // 3
                cnt = 1
                prev = curr
        if remove > 0 and cnt >= 3:
            if cnt % 3 == 0:
                remove -= 1
                replace -= 1
            elif cnt % 3 == 1:
                remove2 += 1
        replace += cnt // 3
        use2 = min(replace, remove2, remove // 2)
        replace -= use2
        remove -= use2 * 2

        use3 = min(replace, remove // 3)
        replace -= use3
        remove -= use3 * 3
        return n - 20 + max(replace, 3 - types)

Complexity

Measure	Complexity
Time	O(n log n)
Space	O(1) to O(n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 420. Strong Password Checker is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 420. Strong Password Checker?: LeetCode 420. Strong Password Checker is rated Hard on LeetCode.
What topics does LeetCode 420. Strong Password Checker cover?: LeetCode 420. Strong Password Checker is tagged Greedy, String and Heap (Priority Queue) on LeetCode.