Jobs

Interviews

Discussions

Strong Password Checker

Hard

Amazon

7 views

Topics:

StringsGreedy Algorithms

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., "Baaaabb0" 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.

Examples:

Example 1: Input: password = "a" Output: 5

Example 2: Input: password = "aA1" Output: 3

Example 3: Input: password = "1337C0d3" Output: 0

What is the most efficient way to solve this problem?

Strong Password Checker

Hard

Amazon

7 views

Topics:

StringsGreedy Algorithms

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., "Baaaabb0" 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.

Examples:

Example 1: Input: password = "a" Output: 5

Example 2: Input: password = "aA1" Output: 3

Example 3: Input: password = "1337C0d3" Output: 0

What is the most efficient way to solve this problem?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the minimum and maximum length allowed for the password?
Besides lowercase, uppercase, and digits, are any other characters (e.g., special symbols) allowed in the password, and if so, should they be considered when calculating the minimum number of steps?
If the password already meets the minimum requirements (length, one lowercase, one uppercase, one digit), should I return 0?
In the case of multiple violations, should I prioritize fixing length violations before addressing missing character type violations?
Are there any specific character restrictions or disallowed character sequences that should trigger additional penalties?

Brute Force Solution

Approach

The brute force method for the password checker is like trying every possible password combination. We generate passwords systematically, and for each one, check if it meets all the strength requirements. If it doesn't, we move to the next password until we find the shortest one that satisfies all criteria.

Here's how the algorithm would work step-by-step:

Start with a password that is very short, like just one character.
Then, systematically try every possible character for that single position: letters (uppercase and lowercase), numbers, and symbols.
Next, move on to passwords of length two, trying every possible combination of two characters.
Continue increasing the password length one character at a time, always trying every possible character for each position.
For each potential password we create, check if it meets all the password strength requirements (minimum length, at least one uppercase letter, at least one lowercase letter, at least one digit, no repeating characters).
If a password meets all the requirements, remember its length.
Keep going until you have checked passwords long enough so you know you've found the absolute shortest valid password you could have created. This may involve a smart way to terminate early. For example, we can stop as soon as we find a valid password if we are confident that it is the shortest possible password length.
The length of that shortest valid password is our answer (or, if our initial password was too short to begin with, the difference between it's length and the minimum allowed length is our answer).

Code Implementation

def strong_password_checker_brute_force(password):
    minimum_length = 6
    maximum_length = 20

    # We start from a minimum possible password length and try all
    for password_length in range(1, maximum_length + 1):
        possible_characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-+"
        
        # Recursively generate every possible password of current length
        def generate_passwords(current_length, current_password):
            if current_length == 0:
                if is_valid_password(current_password):
                    return current_password
                else:
                    return None
            
            for character in possible_characters:
                result = generate_passwords(current_length - 1, character + current_password)
                if result:
                    return result
            return None

        shortest_valid_password = generate_passwords(password_length, "")

        # If we found a valid password, we can stop early.
        if shortest_valid_password:
            if len(password) < minimum_length:
                return minimum_length - len(password)
            else:
                return len(shortest_valid_password) - len(password)
    
    # Helper function to determine password validity
    def is_valid_password(password_to_check):
        has_lowercase = any(character.islower() for character in password_to_check)
        has_uppercase = any(character.isupper() for character in password_to_check)
        has_digit = any(character.isdigit() for character in password_to_check)
        no_repeating = all(password_to_check[i] != password_to_check[i+1] for i in range(len(password_to_check) - 1)) if len(password_to_check) > 1 else True

        # Check that the password length meets requirements
        if len(password_to_check) < minimum_length or len(password_to_check) > maximum_length:
            return False

        # Password must meet these 3 character variety requirements
        if not (has_lowercase and has_uppercase and has_digit):
            return False

        # Password must not have repeating characters
        if not no_repeating:
            return False

        return True
    
    return 0

Big(O) Analysis

Time Complexity

O(m^n) – The brute force approach tries every possible password combination up to a certain length. Let 'm' be the number of possible characters (uppercase, lowercase, digits, symbols). For a password of length 'n', we are essentially exploring 'm' options for each position. Therefore, the algorithm generates passwords of length 1, then length 2, then length 3, and so on, until a valid password is found. In the worst case, we might have to check all possible combinations up to a length where a valid password is found or a maximum allowable length is reached, resulting in a time complexity of O(m^1 + m^2 + ... + m^n), which is dominated by O(m^n).

Space Complexity

O(1) – The provided brute force method generates and checks passwords one at a time. It doesn't explicitly store a collection of invalid passwords or intermediate results. The algorithm primarily uses a single password string which is repeatedly overwritten and checked. Therefore, the auxiliary space used is constant, independent of the input password length, primarily for variables to track the current password being tested and its length, as well as boolean flags for the password requirements.

Optimal Solution

Approach

The goal is to make a password strong by making the fewest changes possible. The strategy is to identify what the password is missing (length, character types) and then fix the biggest problems first.

Here's how the algorithm would work step-by-step:

First, figure out if the password is too short, too long, or just right.
If it's too short, you need to add characters. If it's too long, you need to remove characters.
Next, see what character types are missing: lowercase, uppercase, and digits.
If the password is too long, focus on removing repeating characters first because this often helps meet the character type requirements too. Remove longer repeating sequences before shorter ones.
If the password is too short, try to insert characters strategically to fix both length and character type requirements at the same time. Add characters where repetitions exist if possible to break them up while adding necessary character diversity.
If it's the right length but missing character types, change some characters to meet those requirements, focusing on spots where repeating characters occur or at the beginning or end.
The final count of changes (insertions, deletions, replacements) is the answer.

Code Implementation

def strong_password_checker(password):
    password_length = len(password)
    changes_needed = 0
    missing_lower = not any(character.islower() for character in password)
    missing_upper = not any(character.isupper() for character in password)
    missing_digit = not any(character.isdigit() for character in password)
    missing_count = missing_lower + missing_upper + missing_digit

    if password_length < 6:
        changes_needed += max(missing_count, 6 - password_length)
    elif password_length > 20:
        difference = password_length - 20
        changes_needed += difference

        # Prioritize removing longer repeating sequences
        repeating_groups = []
        index = 0
        while index < password_length:
            length = 1
            while index + length < password_length and password[index + length] == password[index]:
                length += 1
            if length >= 3:
                repeating_groups.append((length, index))
            index += length

        repeating_groups.sort(reverse=True)

        reduction_map = [0] * password_length
        for length, index in repeating_groups:
            if difference <= 0:
                break
            reduction_size = min(length // 3, difference)
            for i in range(index, index + reduction_size * 3, 3):
                reduction_map[i] = 1
            difference -= reduction_size

        missing_count = max(0, missing_count - sum(reduction_map))
        changes_needed += missing_count

    else:
        # Password length is within acceptable range
        index = 0
        repeating_count = 0
        while index < password_length:
            length = 1
            while index + length < password_length and password[index + length] == password[index]:
                length += 1
            if length >= 3:
                repeating_count += length // 3
            index += length

        # Replacing characters for missing types
        changes_needed += max(missing_count, repeating_count)

    return changes_needed

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the password string of length n multiple times, but each iteration performs a linear operation. The steps for checking length, character types, and identifying repeating characters each take O(n) time. Removing or inserting characters, though potentially shifting other characters, can be done in O(n) time overall. Therefore, the dominant factor is the linear iteration through the string, resulting in O(n) time complexity.

Space Complexity

O(N) – The space complexity is determined by the 'repeating characters' analysis where we might need to store information about repeating sequences. In the worst case, the password might consist of only one repeating character (e.g., 'aaaaaaaaaa'), which could lead to storing N elements related to that repeating sequence, where N is the length of the password. This auxiliary space requirement results in O(N) space complexity as the size of the storage scales linearly with the input size. Other variables used are constant and don't affect the overall space complexity.

Edge Cases

Case	How to Handle
Null or Empty Password	Return the minimum number of operations (3) as an empty password needs at least one of each character type added and at least the minimum length reached.
Password length is exactly equal to the minimum requirement (6), but doesn't meet all character requirements.	Calculate the number of missing character types and return the maximum of that number and the number of replacements needed.
Password length exceeds the maximum (20) with repeating character sequences and missing character types.	Prioritize deletions to reduce the length, and then apply replacement operations strategically, giving preference to the most frequent repeating sequences.
Password contains only one type of character (e.g., 'aaaaaaaaaa').	Replace characters within repeating sequences to introduce the missing character types after any necessary deletions.
Long repeating sequences (length > 3) appear multiple times throughout the password.	Greedily target the longest repeating sequences first for deletion or replacement to minimize the number of operations.
Password meets length and character type requirements but has many short repeating sequences (length 3).	Replace characters within these sequences to break them up without increasing length, then check the number of missing types.
Integer overflow during calculations of needed deletions/insertions/replacements.	Use `long` or equivalent data type to store intermediate operation counts and avoid overflow, casting back to `int` only for the final result ensuring it fits within the valid range.
Password length is close to minimum length 6 and requires insertions to satisfy character criteria.	Prioritize insertions of missing character types over replacements of existing characters to satisfy all conditions with minimum operations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the minimum and maximum length allowed for the password?
Besides lowercase, uppercase, and digits, are any other characters (e.g., special symbols) allowed in the password, and if so, should they be considered when calculating the minimum number of steps?
If the password already meets the minimum requirements (length, one lowercase, one uppercase, one digit), should I return 0?
In the case of multiple violations, should I prioritize fixing length violations before addressing missing character type violations?
Are there any specific character restrictions or disallowed character sequences that should trigger additional penalties?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with a password that is very short, like just one character.
Then, systematically try every possible character for that single position: letters (uppercase and lowercase), numbers, and symbols.
Next, move on to passwords of length two, trying every possible combination of two characters.
Continue increasing the password length one character at a time, always trying every possible character for each position.
For each potential password we create, check if it meets all the password strength requirements (minimum length, at least one uppercase letter, at least one lowercase letter, at least one digit, no repeating characters).
If a password meets all the requirements, remember its length.
Keep going until you have checked passwords long enough so you know you've found the absolute shortest valid password you could have created. This may involve a smart way to terminate early. For example, we can stop as soon as we find a valid password if we are confident that it is the shortest possible password length.
The length of that shortest valid password is our answer (or, if our initial password was too short to begin with, the difference between it's length and the minimum allowed length is our answer).

Code Implementation

def strong_password_checker_brute_force(password):
    minimum_length = 6
    maximum_length = 20

    # We start from a minimum possible password length and try all
    for password_length in range(1, maximum_length + 1):
        possible_characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-+"
        
        # Recursively generate every possible password of current length
        def generate_passwords(current_length, current_password):
            if current_length == 0:
                if is_valid_password(current_password):
                    return current_password
                else:
                    return None
            
            for character in possible_characters:
                result = generate_passwords(current_length - 1, character + current_password)
                if result:
                    return result
            return None

        shortest_valid_password = generate_passwords(password_length, "")

        # If we found a valid password, we can stop early.
        if shortest_valid_password:
            if len(password) < minimum_length:
                return minimum_length - len(password)
            else:
                return len(shortest_valid_password) - len(password)
    
    # Helper function to determine password validity
    def is_valid_password(password_to_check):
        has_lowercase = any(character.islower() for character in password_to_check)
        has_uppercase = any(character.isupper() for character in password_to_check)
        has_digit = any(character.isdigit() for character in password_to_check)
        no_repeating = all(password_to_check[i] != password_to_check[i+1] for i in range(len(password_to_check) - 1)) if len(password_to_check) > 1 else True

        # Check that the password length meets requirements
        if len(password_to_check) < minimum_length or len(password_to_check) > maximum_length:
            return False

        # Password must meet these 3 character variety requirements
        if not (has_lowercase and has_uppercase and has_digit):
            return False

        # Password must not have repeating characters
        if not no_repeating:
            return False

        return True
    
    return 0

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out if the password is too short, too long, or just right.
If it's too short, you need to add characters. If it's too long, you need to remove characters.
Next, see what character types are missing: lowercase, uppercase, and digits.
If the password is too long, focus on removing repeating characters first because this often helps meet the character type requirements too. Remove longer repeating sequences before shorter ones.
If the password is too short, try to insert characters strategically to fix both length and character type requirements at the same time. Add characters where repetitions exist if possible to break them up while adding necessary character diversity.
If it's the right length but missing character types, change some characters to meet those requirements, focusing on spots where repeating characters occur or at the beginning or end.
The final count of changes (insertions, deletions, replacements) is the answer.

Code Implementation

def strong_password_checker(password):
    password_length = len(password)
    changes_needed = 0
    missing_lower = not any(character.islower() for character in password)
    missing_upper = not any(character.isupper() for character in password)
    missing_digit = not any(character.isdigit() for character in password)
    missing_count = missing_lower + missing_upper + missing_digit

    if password_length < 6:
        changes_needed += max(missing_count, 6 - password_length)
    elif password_length > 20:
        difference = password_length - 20
        changes_needed += difference

        # Prioritize removing longer repeating sequences
        repeating_groups = []
        index = 0
        while index < password_length:
            length = 1
            while index + length < password_length and password[index + length] == password[index]:
                length += 1
            if length >= 3:
                repeating_groups.append((length, index))
            index += length

        repeating_groups.sort(reverse=True)

        reduction_map = [0] * password_length
        for length, index in repeating_groups:
            if difference <= 0:
                break
            reduction_size = min(length // 3, difference)
            for i in range(index, index + reduction_size * 3, 3):
                reduction_map[i] = 1
            difference -= reduction_size

        missing_count = max(0, missing_count - sum(reduction_map))
        changes_needed += missing_count

    else:
        # Password length is within acceptable range
        index = 0
        repeating_count = 0
        while index < password_length:
            length = 1
            while index + length < password_length and password[index + length] == password[index]:
                length += 1
            if length >= 3:
                repeating_count += length // 3
            index += length

        # Replacing characters for missing types
        changes_needed += max(missing_count, repeating_count)

    return changes_needed

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty Password	Return the minimum number of operations (3) as an empty password needs at least one of each character type added and at least the minimum length reached.
Password length is exactly equal to the minimum requirement (6), but doesn't meet all character requirements.	Calculate the number of missing character types and return the maximum of that number and the number of replacements needed.
Password length exceeds the maximum (20) with repeating character sequences and missing character types.	Prioritize deletions to reduce the length, and then apply replacement operations strategically, giving preference to the most frequent repeating sequences.
Password contains only one type of character (e.g., 'aaaaaaaaaa').	Replace characters within repeating sequences to introduce the missing character types after any necessary deletions.
Long repeating sequences (length > 3) appear multiple times throughout the password.	Greedily target the longest repeating sequences first for deletion or replacement to minimize the number of operations.
Password meets length and character type requirements but has many short repeating sequences (length 3).	Replace characters within these sequences to break them up without increasing length, then check the number of missing types.
Integer overflow during calculations of needed deletions/insertions/replacements.	Use `long` or equivalent data type to store intermediate operation counts and avoid overflow, casting back to `int` only for the final result ensuring it fits within the valid range.
Password length is close to minimum length 6 and requires insertions to satisfy character criteria.	Prioritize insertions of missing character types over replacements of existing characters to satisfy all conditions with minimum operations.