LeetCode 420: Strong Password Checker Solution in Python – A Step-by-Step Guide

What Is LeetCode 420: Strong Password Checker?

In LeetCode 420: Strong Password Checker, you’re given a string password (e.g., "aaaabbbb"), and you need to return the minimum number of operations—insertions, deletions, or replacements—to make it "strong." A strong password must:

• Be 6 to 20 characters long.
• Contain at least one lowercase letter, one uppercase letter, and one digit.
• Have no three consecutive identical characters (e.g., "aaa" is bad).

You can use any operation to fix it, and the goal is the least total moves. For "aaaabbbb" (8 chars, all lowercase, repeating 'a's and 'b's), it takes 4 operations to become "aA1bB2" (6 chars, mixed case, digit, no repeats).

Problem Statement

• Input: A string password.
• Output: An integer—minimum operations to make it strong.
• Rules:
• 6 ≤ length ≤ 20.
• At least one lowercase, uppercase, and digit.
• No three consecutive identical characters.
• Operations: insert, delete, replace.

Constraints

• 0 <= password.length <= 50.
• password contains letters, digits, dots ('.'), or exclamation marks ('!').

Examples

• Input: password = "a"
• Output: 5 (add 5 chars for length, case, digit).
• Input: password = "aaa"
• Output: 3 (replace 'a' to break repeat, add case, digit).
• Input: password = "aaaabbbb"
• Output: 4 (e.g., "aA1bB2").

Understanding the Problem: Strengthening the Password

To solve LeetCode 420: Strong Password Checker in Python, we need to calculate the fewest operations to meet all strong password rules. A brute-force idea might be to try every possible tweak—but with up to 50 characters and multiple rules, that’s a mess! Instead, we’ll use:

• Best Solution (Greedy with Repetition Handling): O(n) time, O(1) space—optimizes moves smartly.
• Alternative Solution (Brute Force Simulation): O(n * 2^n) time, O(n) space—tries adjustments exhaustively.

Let’s dive into the greedy solution with a clear, step-by-step explanation.

Best Solution: Greedy with Repetition Handling

Why This Is the Best Solution

The greedy with repetition handling method is the top pick because it’s fast—O(n) time, O(1) space—and elegantly balances all rules in one pass. It counts missing character types, calculates length adjustments, and minimizes replacements for repeats using a greedy strategy based on remainder patterns. It’s like fixing a password with a checklist, tackling each issue as efficiently as possible!

How It Works

Think of the password as a project with three tasks:

• Step 1: Check Length:
• If < 6, add = 6 - length.
• If > 20, delete = length - 20.
• Else, no length adjustment.
• Step 2: Check Character Types:
• Count missing: lowercase, uppercase, digit (e.g., "aaa" → 2 missing).
• type_change = number of missing types.
• Step 3: Handle Repeats:
• Find runs of 3+ identical chars (e.g., "aaaa" → length 4).
• Group by length % 3 (0, 1, 2):
• 0: Replace every 3rd (e.g., 6 → 2 replacements).
• 1: Replace every 3rd + 1 (e.g., 4 → 1).
• 2: Replace every 3rd (e.g., 5 → 2).
• rep_change = total replacements needed.
• Step 4: Optimize Moves:
• Length < 6: Max of add and max(type_change, rep_change).
• Length 6-20: Max of type_change and rep_change.
• Length > 20: delete + max of remaining adjustments.
• Step 5: Why This Works:
• Greedy minimizes replacements by prioritizing remainder 0, 1, 2.
• Combines operations (e.g., replace fixes type and repeat).
• It’s like juggling fixes to hit all rules with the least effort!

Step-by-Step Example

Example: password = "aaaabbbb"

• Length: 8 (6-20, no add/delete).
• Types: All lowercase, missing uppercase and digit, type_change = 2.
• Repeats:
• "aaaa": length 4, 4 % 3 = 1, replacements = 1 (e.g., "aaxa").
• "bbbb": length 4, 4 % 3 = 1, replacements = 1.
• rep_change = 1 + 1 = 2.
• Moves: Max(type_change, rep_change) = max(2, 2) = 2.
• Adjust: Need 2 more for types (e.g., "aAabBbb" → "aA1bB2"), total = 4.
• Result: 4.

Example: password = "aaa"

• Length: 3, add = 6 - 3 = 3.
• Types: Missing 2, type_change = 2.
• Repeats: "aaa", length 3, 3 % 3 = 0, rep_change = 1.
• Moves: Max(add, max(type_change, rep_change)) = max(3, max(2, 1)) = 3.
• Result: 3 (e.g., "aax12").

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def strongPasswordChecker(self, password: str) -> int:
        n = len(password)

        # Step 1: Check character types
        has_lower = any(c.islower() for c in password)
        has_upper = any(c.isupper() for c in password)
        has_digit = any(c.isdigit() for c in password)
        type_change = 3 - (has_lower + has_upper + has_digit)

        # Step 2: Handle length
        if n < 6:
            add = 6 - n
            delete = 0
        elif n > 20:
            add = 0
            delete = n - 20
        else:
            add = delete = 0

        # Step 3: Handle repeats
        rep_change = [0, 0, 0]  # Count for lengths % 3 = 0, 1, 2
        i = 0
        while i < n:
            start = i
            while i < n and password[i] == password[start]:
                i += 1
            length = i - start
            if length >= 3:
                rep_change[length % 3] += length // 3

        # Step 4: Optimize with deletions
        total_rep = sum(rep_change)
        if delete > 0:
            # Reduce repeats with deletions
            for k in range(3):  # Prioritize remainder 0, 1, 2
                for d in range(k, delete + 1, 3):
                    if rep_change[k] > 0:
                        reduce = min(rep_change[k], (delete - d) // 3 + 1)
                        rep_change[k] -= reduce
                        delete -= reduce * k
                        total_rep -= reduce
                    if delete <= 0:
                        break
                if delete <= 0:
                    break

        # Step 5: Calculate total moves
        if n < 6:
            return max(add, type_change, total_rep)
        elif n <= 20:
            return max(type_change, total_rep)
        else:
            return delete + max(type_change, total_rep)

• Line 4: Get password length n.
• Line 7-10: Count missing types:
• type_change: 3 - (has_lower + has_upper + has_digit).
• Line 13-18: Handle length:
• < 6: add = 6 - n.
• > 20: delete = n - 20.
• 6-20: No adjustment.
• Line 21-29: Count repeats:
• rep_change: Array for remainders 0, 1, 2.
• Loop finds runs (e.g., "aaaa" → length 4, rep_change[1] += 1).
• Line 32-45: Optimize with deletions:
• Reduce repeats by deleting (e.g., remainder 0 uses 0 deletes per replace).
• Update total_rep and delete.
• Line 48-52: Total moves:
• < 6: Max of add, type_change, rep_change.
• 6-20: Max of type_change, rep_change.
• > 20: delete + max of remaining.
• Time Complexity: O(n)—one pass for repeats, constant loops.
• Space Complexity: O(1)—fixed-size array.

This is like tweaking a password with a smart checklist!

Alternative Solution: Brute Force Simulation

Why an Alternative Approach?

The brute force simulation tries all possible operations step-by-step, adjusting length, types, and repeats. It’s O(n * 2^n) time and O(n) space—intuitive but impractical for large inputs. It’s like testing every fix combo until the password’s strong!

How It Works

Picture it as trial and error:

• Step 1: Start with original password.
• Step 2: Try add/delete/replace to fix rules.
• Step 3: Track min operations.

Step-by-Step Example

Example: password = "aaa"

• Try: Add "123" → "aaa123", replace "a" → "aA123", 3 moves.
• Result: 3.

Code for Brute Force Approach (Simplified)

Copy codeclass Solution:
    def strongPasswordChecker(self, password: str) -> int:
        def is_strong(s):
            if len(s) < 6 or len(s) > 20:
                return False
            if not any(c.islower() for c in s) or \
               not any(c.isupper() for c in s) or \
               not any(c.isdigit() for c in s):
                return False
            for i in range(len(s) - 2):
                if s[i] == s[i+1] == s[i+2]:
                    return False
            return True

        def simulate(s, moves):
            if is_strong(s):
                return moves
            return float('inf')

        # Simplified brute force (not full implementation)
        min_moves = float('inf')
        n = len(password)
        if n < 6:
            # Try adding characters
            for i in range(6 - n + 1):
                new_s = password + "aA1"[:i]
                min_moves = min(min_moves, simulate(new_s, i))
        elif n > 20:
            # Try deleting
            min_moves = min(min_moves, n - 20 + simulate(password[:20], n - 20))
        else:
            # Try replacing
            for i in range(n):
                if i + 2 < n and password[i] == password[i+1] == password[i+2]:
                    new_s = password[:i+1] + "1" + password[i+2:]
                    min_moves = min(min_moves, simulate(new_s, 1))

        return min_moves if min_moves != float('inf') else 0

# Note: Full brute force would explore all combinations, impractical here.

• Time Complexity: O(n * 2^n)—exponential due to combinations.
• Space Complexity: O(n)—recursion or string copies.

It’s a slow tweak tester!

Comparing the Two Solutions

• Greedy with Repetition (Best):
• Pros: O(n), O(1), fast and optimal.
• Cons: Complex logic.
• Brute Force (Alternative):
• Pros: O(n * 2^n), O(n), intuitive.
• Cons: Impractical.

Greedy wins for speed.

Additional Examples and Edge Cases

• "a": 5.
• "aaa123": 1.
• **"a" * 21**: 6 (delete 1, fix types/repeats).

Greedy handles all.

Complexity Breakdown

• Greedy: Time O(n), Space O(1).
• Brute Force: Time O(n * 2^n), Space O(n).

Greedy’s the champ.

Key Takeaways

• Greedy: Optimize smart!
• Brute Force: Try it all!
• Passwords: Rules twist.
• Python Tip: Loops rock—see [Python Basics](/python/basics).

Final Thoughts: Strengthen That Pass

LeetCode 420: Strong Password Checker in Python is a password-fixing quest. Greedy with repetition nails it fast, while brute force tests it slow. Want more string fun? Try LeetCode 415: Add Strings or LeetCode 678: Valid Parenthesis String. Ready to tweak? Head to Solve LeetCode 420 on LeetCode and strengthen that password today!