We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Strong Password Checker

Number: 420

Difficulty: Hard

Paid? No

Companies: Microsoft, Flipkart, Google, Apple

Problem Description

A password is considered strong if it meets all of the following conditions:

  • It has between 6 and 20 characters inclusive.
  • 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.

Given a string password, return the minimum number of steps required to transform password into a strong one. In one step, you can insert, delete, or replace a character.

Key Insights

  • Check for missing character types (lowercase, uppercase, digit).
  • Count groups of consecutive repeating characters to detect where replacements are needed.
  • For short passwords (less than 6), the answer is the maximum between missing character types and the number of insertions required.
  • For passwords of acceptable length (6 to 20), focus on performing replacements for groups of repeating characters.
  • For long passwords (more than 20), deletions are required, and strategically deleting characters within repeating groups (especially using mod 3 heuristics) can reduce the number of replacements required.
  • The overall minimum steps are influenced by a combination of deletions (if necessary), replacements, and insertions to fix missing character types.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the password
Space Complexity: O(n) in the worst-case (for storing information about repeating groups)

Solution

The solution works in multiple phases:

  1. Count missing character types.
  2. Identify consecutive repeating sequences and determine how many replacements are needed if no deletions occur.
  3. Handle cases:
    • If the password is too short, return the maximum between missing character types and the number of insertions needed (6 - length).
    • If the password has valid length (6 to 20), the answer is max(missing types, required replacements for repeating groups).
    • If the password is too long (over 20), first compute the number of deletions needed. Then, use deletions in a greedy manner on repeating groups to reduce the replacements by targeting groups with lengths that benefit most from a deletion (those with length % 3 == 0, then % 3 == 1, and so on). Finally, add the number of deletions to the maximum of the missing character types and the adjusted replacement count.

Data structures include arrays/lists to track repeating groups. The approach combines greedy deletions with character type and replacement counting.

Code Solutions

# Python solution for Strong Password Checker

def strongPasswordChecker(password: str) -> int:
    n = len(password)
    missing_lower, missing_upper, missing_digit = 1, 1, 1
    
    # Check for missing character types
    for char in password:
        if char.islower():
            missing_lower = 0
        elif char.isupper():
            missing_upper = 0
        elif char.isdigit():
            missing_digit = 0
    missing_types = missing_lower + missing_upper + missing_digit

    # List to hold lengths of sequences with three or more repeating characters
    repeats = []
    i = 2
    while i < n:
        if password[i] == password[i-1] and password[i-1] == password[i-2]:
            j = i - 2
            while i < n and password[i] == password[j]:
                i += 1
            repeats.append(i - j)
        else:
            i += 1

    total_replacements = sum(length // 3 for length in repeats)
    
    if n < 6:
        return max(missing_types, 6 - n)
    elif n <= 20:
        return max(missing_types, total_replacements)
    else:
        # Number of deletions needed
        deletions = n - 20
        # Try to reduce replacements using deletions
        for k in range(len(repeats)):
            if deletions <= 0:
                break
            if repeats[k] < 3:
                continue
            if repeats[k] % 3 == 0:
                reduction = min(deletions, 1)
                repeats[k] -= reduction
                deletions -= reduction
        
        for k in range(len(repeats)):
            if deletions <= 0:
                break
            if repeats[k] < 3:
                continue
            if repeats[k] % 3 == 1:
                reduction = min(deletions, 2)
                repeats[k] -= reduction
                deletions -= reduction
        
        for k in range(len(repeats)):
            if deletions <= 0:
                break
            if repeats[k] < 3:
                continue
            reduction = min(deletions, repeats[k] - 2)
            repeats[k] -= reduction
            deletions -= reduction

        replacements_after_deletion = sum(length // 3 for length in repeats if length >= 3)
        
        return (n - 20) + max(missing_types, replacements_after_deletion)

# Example usage:
print(strongPasswordChecker("a"))         # Expected output: 5
print(strongPasswordChecker("aA1"))       # Expected output: 3
print(strongPasswordChecker("1337C0d3"))    # Expected output: 0
← Back to All Questions