LeetCode 420: Strong Password Checker

Problem Description

LeetCode Problem 420

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.
• It does not contain three repeating characters in a row (i.e., “Baaabb0” is weak, but “Baaba0” is strong).

Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.

In one step, you can:

• Insert one character to password,
• Delete one character from password, or
• Replace one character of password with another character.

Example 1:

Input: password = “a”
Output: 5

Example 2:

Input: password = “aA1”
Output: 3

Example 3:

Input: password = “1337C0d3”
Output: 0

Constraints:

• 1 <= password.length <= 50
• password consists of letters, digits, dot ’.’ or exclamation mark ’!‘.

Difficulty: Hard

Tags: string, greedy, heap (priority queue)

Rating: 33.98%

Solution Strategy

The solution follows a case-based approach, handling different password lengths differently:

Case 1: Password Length < 6

When the password is too short, we need insertions. The minimum operations needed will be:

max(6 - n, missing)

Where n is the password length and missing is the count of missing character types. We take the maximum because each insertion could potentially also fix a missing character type.

Case 2: Password Length between 6 and 20

For passwords of valid length, we only need to handle:

• Missing character types
• Repeating sequences

We take the maximum of:

• Number of missing character types
• Number of replacements needed to break repeating sequences

Case 3: Password Length > 20

This is the trickiest case. We need to:

1. Delete characters to get to length 20
2. Use those deletions strategically to minimize the replacements needed for repeating sequences
3. Ensure we have all required character types

Detailed Solution Explanation

Let’s go through the solution step by step:

class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        def missing_types(s):
            # Count missing character types (lowercase, uppercase, digit)
            types = 0
            if not any(c.islower() for c in s): types += 1
            if not any(c.isupper() for c in s): types += 1
            if not any(c.isdigit() for c in s): types += 1
            return types
        
        n = len(password)
        missing = missing_types(password)

The helper function missing_types checks how many character types are missing from the password. We use Python’s any() function with generator expressions to efficiently check for the presence of each required character type.

        # Case 1: Length < 6
        if n < 6:
            return max(6 - n, missing)

For short passwords, we need at least enough insertions to reach length 6. Each insertion could potentially add a missing character type, so we take the maximum of needed length and missing types.

        # Count repeating sequences
        replace = 0  # Total replacements needed
        one = 0     # Count of sequences where length % 3 == 0
        two = 0     # Count of sequences where length % 3 == 1
        i = 2
        while i < n:
            if password[i] == password[i-1] == password[i-2]:
                length = 2
                while i < n and password[i] == password[i-1]:
                    length += 1
                    i += 1
                replace += length // 3
                if length % 3 == 0: one += 1
                elif length % 3 == 1: two += 1
            else:
                i += 1

This section counts repeating sequences and categorizes them based on their length modulo 3. This categorization is crucial for optimizing deletions in case 3. For each repeating sequence:

• We need $\left\lfloor \frac{\text{length}}{3} \right\rfloor$ replacements to fix it
• We track sequences of lengths that are multiples of 3 or have remainder 1 when divided by 3

        # Case 2: Length <= 20
        if n <= 20:
            return max(missing, replace)

For valid-length passwords, we simply need enough operations to fix both missing types and repeating sequences.

        # Case 3: Length > 20
        delete = n - 20
        
        # Try to use deletions to reduce replacements needed
        replace -= min(delete, one)
        replace -= min(max(delete - one, 0), two * 2) // 2
        replace -= max(delete - one - 2 * two, 0) // 3
        
        return delete + max(missing, replace)

For long passwords, we use a greedy approach:

1. Calculate required deletions to reach length 20
2. Use deletions strategically to reduce needed replacements:
   • First on sequences of length divisible by 3 (one deletion saves one replacement)
   • Then on sequences of length with remainder 1 (two deletions save one replacement)
   • Finally on remaining sequences (three deletions save one replacement)

Complexity Analysis

• Time Complexity: $O(n)$, where n is the length of the password

  • We make a single pass through the password to count character types
  • Another pass to identify repeating sequences
  • All other operations are constant time

• Space Complexity: $O(1)$

  • We only use a constant amount of additional space regardless of input size