Problem Description

You need to check if a given password string is "strong" based on specific criteria.

A password is considered strong if it meets ALL of the following requirements:

1. Length requirement: The password must have at least 8 characters.

2. Character type requirements - The password must contain at least one of each:

   • One lowercase letter (a-z)
   • One uppercase letter (A-Z)
   • One digit (0-9)
   • One special character from this set: "!@#$%^&*()-+"

3. No adjacent duplicates: The password cannot have the same character appearing twice in a row. For example, "aab" fails this check because 'a' appears twice consecutively, but "aba" passes because no adjacent characters are the same.

Given a string password, you need to return true if it satisfies all the above conditions (making it a strong password), or false if it fails any condition.

The solution uses bit manipulation with a mask to track which character types have been found. Each bit in the mask represents:

• Bit 0 (value 1): lowercase letter found
• Bit 1 (value 2): uppercase letter found
• Bit 2 (value 4): digit found
• Bit 3 (value 8): special character found

When all four types are present, the mask equals 15 (binary 1111). The solution also checks for adjacent duplicate characters by comparing each character with the previous one during traversal.

Intuition

The problem requires checking multiple conditions simultaneously. We need to verify the password meets all criteria, not just some of them. This suggests we need a way to track which conditions have been satisfied as we scan through the password.

For the length check and adjacent duplicate check, these are straightforward - we can check the length upfront and compare consecutive characters as we iterate.

The interesting part is tracking the four character type requirements. We need to know if we've seen at least one of each type. A natural approach would be to use four boolean flags, but there's a more elegant solution using bit manipulation.

Think of it this way: we have 4 binary conditions (has lowercase, has uppercase, has digit, has special character). Each can be either true (1) or false (0). We can represent all four states with a single 4-bit number. When we encounter a lowercase letter, we "turn on" bit 0. When we see an uppercase letter, we "turn on" bit 1, and so on.

Using the OR operation (|=) ensures that once a bit is set to 1, it stays 1 even if we encounter more characters of that type. This is perfect because we only care about "at least one" of each type.

By assigning:

• Lowercase → bit 0 (value 1)
• Uppercase → bit 1 (value 2)
• Digit → bit 2 (value 4)
• Special → bit 3 (value 8)

When all four types are present, our mask becomes 1111 in binary, which equals 15 in decimal. This gives us a single final check: mask == 15 tells us if all character types were found.

This approach elegantly combines all character type checks into a single variable and a single final comparison, while we handle the other constraints (length and adjacent duplicates) separately during our single pass through the string.

Solution Approach

The implementation follows a single-pass simulation approach combined with bit manipulation to efficiently check all password requirements.

Step 1: Length Check First, we immediately check if the password length is less than 8. If it is, we return false since this is a fundamental requirement.

if len(password) < 8:
    return False

Step 2: Initialize the Bit Mask We initialize a variable mask = 0 to track which character types we've encountered. This will use 4 bits to represent the presence of each required character type.

Step 3: Single Pass Through Password We iterate through each character with its index using enumerate(password). For each character at position i:

Adjacent Duplicate Check:

• If i > 0 (not the first character), we compare the current character with the previous one
• If c == password[i - 1], we've found adjacent duplicates and return false

Character Type Detection and Bit Setting: We use conditional checks to determine the character type and set the corresponding bit in our mask:

• If c.islower(): Set bit 0 by doing mask |= 1 (binary: 0001)
• If c.isupper(): Set bit 1 by doing mask |= 2 (binary: 0010)
• If c.isdigit(): Set bit 2 by doing mask |= 4 (binary: 0100)
• Otherwise (special character): Set bit 3 by doing mask |= 8 (binary: 1000)

The |= operator performs a bitwise OR, which "turns on" the specific bit without affecting other bits that are already set.

Step 4: Final Validation After traversing the entire password, we check if mask == 15 (binary: 1111). This value indicates all four bits are set, meaning we found at least one character of each required type.

The beauty of this approach is its efficiency:

• Time Complexity: O(n) where n is the password length - we only traverse the string once
• Space Complexity: O(1) - we only use a single integer variable for tracking

The bit manipulation technique elegantly compresses what could have been four separate boolean flags into a single integer, making the final check extremely clean: we simply verify if all bits are set by comparing to 15.

Example Walkthrough

Let's walk through the solution with the password: "Pass1@aa"

Initial Check:

• Length = 8 characters ✓ (meets minimum requirement)
• Initialize mask = 0 (binary: 0000)

Character-by-character traversal:

1. 'P' (index 0):

   • No previous character to compare
   • It's uppercase → mask |= 2 → mask = 2 (binary: 0010)

2. 'a' (index 1):

   • Check: 'a' ≠ 'P' (no adjacent duplicate) ✓
   • It's lowercase → mask |= 1 → mask = 3 (binary: 0011)

3. 's' (index 2):

   • Check: 's' ≠ 'a' (no adjacent duplicate) ✓
   • It's lowercase → mask |= 1 → mask = 3 (binary: 0011, no change)

4. 's' (index 3):

   • Check: 's' = 's' (adjacent duplicate found!) ✗
   • Return false immediately

The password fails because it contains adjacent duplicate 's' characters at positions 2 and 3.

Let's try a valid password: "Ab3$xyz9"

Initial Check:

• Length = 8 characters ✓
• Initialize mask = 0 (binary: 0000)

Character-by-character traversal:

1. 'A' (index 0): uppercase → mask = 2 (binary: 0010)
2. 'b' (index 1): 'b' ≠ 'A' ✓, lowercase → mask = 3 (binary: 0011)
3. '3' (index 2): '3' ≠ 'b' ✓, digit → mask = 7 (binary: 0111)
4. **'$' (index 3):** '$' ≠ '3' ✓, special → mask = 15 (binary: 1111)
5. 'x' (index 4): 'x' ≠ '$' ✓, lowercase → mask = 15 (no change)
6. 'y' (index 5): 'y' ≠ 'x' ✓, lowercase → mask = 15 (no change)
7. 'z' (index 6): 'z' ≠ 'y' ✓, lowercase → mask = 15 (no change)
8. '9' (index 7): '9' ≠ 'z' ✓, digit → mask = 15 (no change)

Final Check:

• No adjacent duplicates found ✓
• mask == 15 (binary: 1111) ✓ (all character types present)
• Return true

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the password string. The algorithm iterates through each character in the password exactly once using a single for loop. Within each iteration, all operations (character comparison, checking character type with islower(), isupper(), isdigit(), and bitwise OR operations) are performed in constant time O(1).

The space complexity is O(1). The algorithm uses only a fixed amount of extra space regardless of the input size. The variables used are:

• mask: a single integer variable for tracking character type requirements
• i: the loop counter
• c: the current character reference

These variables occupy constant space that doesn't scale with the input size n.

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

Common Pitfalls

1. Incorrect Special Character Validation

The current solution assumes ANY character that isn't a letter or digit is a special character. This is incorrect according to the problem requirements, which specify only these characters are valid: "!@#$%^&*()-+".

Problematic Example:

password = "Abc123[]"  # Contains '[' and ']' which aren't valid special characters
# Current code would incorrectly return True

Solution:

def strongPasswordCheckerII(self, password: str) -> bool:
    if len(password) < 8:
        return False
  
    character_type_mask = 0
    special_chars = "!@#$%^&*()-+"  # Define valid special characters
  
    for index, char in enumerate(password):
        if index > 0 and char == password[index - 1]:
            return False
      
        if char.islower():
            character_type_mask |= 1
        elif char.isupper():
            character_type_mask |= 2
        elif char.isdigit():
            character_type_mask |= 4
        elif char in special_chars:  # Check against valid special characters only
            character_type_mask |= 8
        # If char doesn't match any category, it's invalid but we continue checking
  
    return character_type_mask == 15

2. Assuming All Characters Are Valid

The original code doesn't validate that all characters in the password are from allowed character sets. A password containing invalid characters (like spaces or other symbols) might pass validation.

Problematic Example:

password = "Abc123!€"  # Contains '€' which isn't in any valid category
# Current code would process this without detecting the invalid character

Enhanced Solution with Character Validation:

def strongPasswordCheckerII(self, password: str) -> bool:
    if len(password) < 8:
        return False
  
    character_type_mask = 0
    special_chars = set("!@#$%^&*()-+")  # Use set for O(1) lookup
  
    for index, char in enumerate(password):
        if index > 0 and char == password[index - 1]:
            return False
      
        # Track if character belongs to any valid category
        valid_char = False
      
        if char.islower():
            character_type_mask |= 1
            valid_char = True
        elif char.isupper():
            character_type_mask |= 2
            valid_char = True
        elif char.isdigit():
            character_type_mask |= 4
            valid_char = True
        elif char in special_chars:
            character_type_mask |= 8
            valid_char = True
      
        # If character doesn't belong to any valid category, password is invalid
        if not valid_char:
            return False
  
    return character_type_mask == 15

3. Edge Case with Empty or Very Short Passwords

While the length check handles passwords shorter than 8 characters, it's worth noting that empty strings or single-character passwords will correctly fail, but developers might forget to test these edge cases.

Test Cases to Remember:

assert strongPasswordCheckerII("") == False  # Empty string
assert strongPasswordCheckerII("A") == False  # Single character
assert strongPasswordCheckerII("Aa1!Bb2@") == True  # Valid password
assert strongPasswordCheckerII("Aa1!Bb2") == False  # Only 7 characters