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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Strong Password Checker

Difficulty: Hard

Problem Description

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.

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.

Key Insights

  • The password must meet length requirements (6 to 20 characters).
  • The password must contain at least one lowercase letter, one uppercase letter, and one digit.
  • Consecutive repeating characters must be reduced to at most two in a row.
  • The number of required operations (insert, delete, replace) must be calculated efficiently.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the password, since we need to iterate through the string to check conditions. Space Complexity: O(1), as we only use a fixed amount of space for counters and flags.

Solution

We will use counters to track:

  1. The number of missing character types (lowercase, uppercase, digit).
  2. The number of sequences of three or more repeating characters.

We will first check the length of the password:

  • If it's less than 6, we need to insert characters.
  • If it's more than 20, we need to delete characters.

During this process, we will also count the types of characters present and check for repeating sequences. After gathering all necessary information, we will compute the total number of operations needed based on the conditions outlined.

Code Solutions

def strongPasswordChecker(password: str) -> int:
    n = len(password)
    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)
    
    missing_types = 0
    if not has_lower: missing_types += 1
    if not has_upper: missing_types += 1
    if not has_digit: missing_types += 1

    repeat_count = 0
    i = 2
    while i < n:
        if password[i] == password[i - 1] == password[i - 2]:
            repeat_length = 2
            while i < n and password[i] == password[i - 1]:
                repeat_length += 1
                i += 1
            repeat_count += repeat_length // 3
        else:
            i += 1
    
    if n < 6:
        return max(missing_types, 6 - n)
    elif n <= 20:
        return max(missing_types, repeat_count)
    else:
        excess_length = n - 20
        replace_count = min(excess_length, repeat_count)
        repeat_count -= replace_count
        excess_length -= replace_count
        
        replace_count += excess_length // 3
        return (n - 20) + max(missing_types, repeat_count)
← Back to All Questions