2299. Strong Password Checker II

Problem Description

The problem presents a scenario where we need to validate a string, password, to determine if it qualifies as a strong password. For a password to be considered strong, it must meet all these criteria:

1. The length of the password must be at least 8 characters.
2. It must include at least one lowercase letter.
3. It must include at least one uppercase letter.
4. It must have at least one digit.
5. It must contain at least one special character, which must be from the set !@#$%^&*()-+.
6. It must not have more than one identical character in a row, meaning no two adjacent characters can be the same.

The goal is to write a function that returns true if the password meets all the above-described conditions, otherwise returns false.

Intuition

The intuition behind the solution is to go through the password character by character to check if it meets all the necessary criteria for being strong. We can do this by iterating through the string and using flags to mark if we've detected each type of required character. Here's the step-by-step process:

1. Length Check: First, we check if the password has at least 8 characters. If it's shorter, we immediately return false.

2. Adjacency Check: As we iterate, we check if the current character is the same as the previous one - if it is, we return false because this violates the non-adjacent character condition.

3. Character Type Checks: For every character, we need to check if it is a lowercase letter, an uppercase letter, a digit, or a special character. We can do this using the .islower(), .isupper(), .isdigit() methods, and by verifying if the character is in the specified special characters string.

4. Aggregation with Bitmasking: Instead of keeping four separate flags, we can use a bitmask (mask) to aggregate all the flags into a single integer. Bitwise OR operations |= are used to set the corresponding bits when we encounter lowercase letters, uppercase letters, digits, and special characters. Each character type corresponds to a different bit in the mask, so for example:

   • If we encounter a lowercase letter, we set the first bit (mask |= 1).
   • For an uppercase letter, the second bit (mask |= 2), and so on.

5. Final Verification: After going through every character of the password, we check if the mask equals 15 (binary 1111). This means that all four bits are set, so every type of required character is included in the password at least once.

The code is efficient and compact. By using bit operations, it avoids the use of multiple boolean variables and reduces the number of conditions checked.

Solution Approach

The implementation of the solution involves a simple yet effective approach by scanning through each character in the password and using bitwise operations to track whether the password criteria have been met. Here’s a detailed walk-through:

1. Initial Length Check: Immediately check if the password is less than 8 characters. If so, the function returns false.

   • if len(password) < 8: return False

2. Setup: Initialize a variable mask to 0. This will serve as a 4-bit mask where each bit represents the presence of a different character type (lowercase, uppercase, digit, special character).

3. Iterate Through Password Characters: By using a for loop with enumeration, we iterate over the password's characters, keeping track of each character and its index.

   • for i, c in enumerate(password):

4. Adjacency Check: Inside the loop, we first check if the current character is the same as the previous one. If that’s the case, we immediately return false since this violates the non-adjacent identical character condition.

   • if i and c == password[i - 1]: return False

5. Character Type Detection: Still in the loop, we check the type of the current character:

   • If it’s a lowercase letter (c.islower()), set the first bit of the mask (mask |= 1).
   • If it’s an uppercase letter (c.isupper()), set the second bit of the mask (mask |= 2).
   • If it’s a digit (c.isdigit()), set the third bit of the mask (mask |= 4).
   • If it’s a special character (checked by seeing if it is not any of the above types), set the fourth bit of the mask (mask |= 8).

6. Final Verification: After the loop, we check if all the bits are set in the mask by comparing it to 15 (binary 1111). This means all required character types are present in the password. The function returns true if mask == 15; otherwise, it returns false.

7. Data Structures, Algorithms & Patterns:

   • Data Structure: A single integer variable is used for tracking the presence of character types through a concept called bitmasking.
   • Algorithms: A single pass through the string is the main algorithmic component. All checks are done in this single pass, making the time complexity O(n) with n as the password length.
   • Patterns: The solution uses bitwise operations to aggregate checks into a single value, reducing the need for multiple variables.

The simplicity and efficiency of the bitwise operations are key in making the code concise and performant. The choice to use a bitmask over multiple boolean variables exemplifies a common pattern in problems where aggregating flags into a single integer helps optimize space and improve code readability.

Example Walkthrough

Let's consider the password string password as Aa1!Aa1!. To determine if this is a strong password according to the given criteria, our function will proceed as follows:

1. Initial Length Check: Our password Aa1!Aa1! is 8 characters long, so it passes the length requirement.

2. Setup: We initialize the mask to 0. This mask will help us track whether we have encountered at least one lowercase letter, uppercase letter, digit, and special character.

3. Iterate Through Password Characters: We start looping through each character in the password.

4. Adjacency Check:

   • For the first character 'A', there is no previous character, so we move on to type checking.
   • The second character 'a' is different from the first, so no adjacency violation occurs.
   • This process continues, and since no adjacent characters are identical, no adjacency checks fail.

5. Character Type Detection: As we go through each character:

   • For 'A': It's uppercase, so we set the second bit of the mask (mask |= 2).
   • For 'a': It's lowercase, so we set the first bit of the mask (mask |= 1).
   • For '1': It's a digit, so we set the third bit of the mask (mask |= 4).
   • For '!': It's a special character, so we set the fourth bit of the mask (mask |= 8).
   • As we continue through each character, no additional bits are set since each type has already been encountered.

6. Final Verification: At the end, our mask is 1111 in binary, or 15 in decimal, which means all types of required characters were present at least once.

7. Data Structures, Algorithms & Patterns: The use of bitmasking to track character types in a single integer is an efficient data structure choice, and iterating through the password is the primary algorithm. No patterns are additional, and the bitwise operations signify a common pattern to optimize space and improve code readability.

The password Aa1!Aa1! is therefore confirmed to be a strong password by our implementation.

Solution Implementation

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the length of the password string. This is because the function consists of a single for loop that iterates through each character of the password string exactly once, performing a constant number of operations per character.

The space complexity of the code is O(1). The extra space used by the function is constant and does not depend on the size of the input password string. The variables used (mask and c) require a fixed amount of space and their size does not scale with the input.

Learn more about how to find time and space complexity quickly using problem constraints.