LeetCode 3941 - Password Strength

LeetCode Problem 3941

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

The problem requires calculating the strength of a password based on its distinct characters. Each character type contributes differently to the strength: lowercase letters add 1 point, uppercase letters add 2 points, digits add 3 points, and special characters from "!@#$" add 5 points. Importantly, each character is counted only once, even if it appears multiple times in the string.

The input is a single string password with a length up to 10^5. It contains only lowercase letters, uppercase letters, digits, and the four specified special characters. The output is a single integer representing the computed strength.

Key points to note are that duplicates should not increase the score, and only characters in the allowed set contribute. Edge cases include passwords with all identical characters, passwords containing only one character type, or passwords with all four types.

The constraints indicate that the input can be very large, so an efficient linear solution is required.

Approaches

Brute-Force Approach

A naive approach would iterate through all characters and for each character, check whether it has already been counted using a list or string. If not, add the appropriate score. While this works for small inputs, using a list to store seen characters results in O(n²) time complexity in the worst case due to repeated membership checks.

Optimal Approach

The key observation is that we only need distinct characters and a way to quickly classify them. Using a hash set allows O(1) membership checks and ensures each character is counted only once. Iterating through the string once and maintaining four sets (for lowercase, uppercase, digits, and special characters) allows us to compute the score in O(n) time, which is efficient for the input constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Checks membership in a list for each character
Optimal	O(n)	O(1)	Uses sets for each character type; size of sets is bounded (26 lowercase, 26 uppercase, 10 digits, 4 specials)

Algorithm Walkthrough

1. Initialize four empty sets to track distinct lowercase letters, uppercase letters, digits, and special characters.
2. Iterate over each character ch in the password string.
3. Check the type of ch:

• If ch is a lowercase letter, add it to the lowercase set.
• If ch is an uppercase letter, add it to the uppercase set.
• If ch is a digit, add it to the digits set.
• If ch is in "!@#$", add it to the special set.

4. After processing all characters, compute the strength as 1 * len(lowercase) + 2 * len(uppercase) + 3 * len(digits) + 5 * len(specials).
5. Return the computed strength.

Why it works: By using sets, we guarantee that each distinct character is counted only once. The classification ensures that each character contributes the correct point value based on its type. The final computation sums the contributions from all sets.

Python Solution

class Solution:
    def passwordStrength(self, password: str) -> int:
        lowercase = set()
        uppercase = set()
        digits = set()
        specials = set("!@#$")
        found_specials = set()
        
        for ch in password:
            if 'a' <= ch <= 'z':
                lowercase.add(ch)
            elif 'A' <= ch <= 'Z':
                uppercase.add(ch)
            elif '0' <= ch <= '9':
                digits.add(ch)
            elif ch in specials:
                found_specials.add(ch)
        
        strength = len(lowercase) * 1 + len(uppercase) * 2 + len(digits) * 3 + len(found_specials) * 5
        return strength

Explanation: The code initializes four sets to track distinct character types. The loop classifies each character efficiently using range checks for letters and digits, and membership check for specials. The final strength is calculated by multiplying the size of each set by its point value.

Go Solution

func passwordStrength(password string) int {
    lowercase := make(map[rune]bool)
    uppercase := make(map[rune]bool)
    digits := make(map[rune]bool)
    specials := map[rune]bool{'!': true, '@': true, '#': true, '$': true}
    foundSpecials := make(map[rune]bool)

    for _, ch := range password {
        if ch >= 'a' && ch <= 'z' {
            lowercase[ch] = true
        } else if ch >= 'A' && ch <= 'Z' {
            uppercase[ch] = true
        } else if ch >= '0' && ch <= '9' {
            digits[ch] = true
        } else if specials[ch] {
            foundSpecials[ch] = true
        }
    }

    strength := len(lowercase)*1 + len(uppercase)*2 + len(digits)*3 + len(foundSpecials)*5
    return strength
}

Explanation: Go uses map[rune]bool for sets. The logic mirrors the Python solution. Ranges for letters and digits are checked, and a separate map tracks special characters. The final score is computed similarly.

Worked Examples

Example 1: password = "aA1!"

Step	Character	lowercase	uppercase	digits	specials	Strength
1	'a'	{'a'}	{}	{}	{}	-
2	'A'	{'a'}	{'A'}	{}	{}	-
3	'1'	{'a'}	{'A'}	{'1'}	{}	-
4	'!'	{'a'}	{'A'}	{'1'}	{'!'}	1 + 2 + 3 + 5 = 11

Example 2: password = "bbB11#"

Step	Character	lowercase	uppercase	digits	specials	Strength
1	'b'	{'b'}	{}	{}	{}	-
2	'b'	{'b'}	{}	{}	{}	-
3	'B'	{'b'}	{'B'}	{}	{}	-
4	'1'	{'b'}	{'B'}	{'1'}	{}	-
5	'1'	{'b'}	{'B'}	{'1'}	{}	-
6	'#'	{'b'}	{'B'}	{'1'}	{'#'}	1 + 2 + 3 + 5 = 11

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Iterate through the string once, each character classified in O(1)
Space	O(1)	Sets are bounded in size: 26 lowercase, 26 uppercase, 10 digits, 4 specials, so memory is constant

The linear time complexity ensures scalability to the maximum input length of 10^5, while the constant space ensures memory efficiency.

Test Cases

# provided examples
assert Solution().passwordStrength("aA1!") == 11  # distinct characters of all types
assert Solution().passwordStrength("bbB11#") == 11  # repeated characters

# boundary cases
assert Solution().passwordStrength("a") == 1  # single lowercase
assert Solution().passwordStrength("A") == 2  # single uppercase
assert Solution().passwordStrength("1") == 3  # single digit
assert Solution().passwordStrength("!") == 5  # single special

# edge cases
assert Solution().passwordStrength("aaaaaaaa") == 1  # all same lowercase
assert Solution().passwordStrength("AAAA") == 2  # all same uppercase
assert Solution().passwordStrength("1111") == 3  # all same digit
assert Solution().passwordStrength("!!!!") == 5  # all same special

# mixed types
assert Solution().passwordStrength("abcABC123!@#") == 1*3 + 2*3 + 3*3 + 5*3  # all distinct

Test	Why
"aA1!"	all four types, single occurrence
"bbB11#"	duplicates should not increase score
"a"	smallest input, lowercase only
"!"	smallest input, special only
"abcABC123!@#"	multiple distinct characters from all categories

Edge Cases

Single character input: A password of length 1 tests that the implementation handles minimal input correctly. The code correctly identifies the type and assigns the proper score.

Repeated characters: Passwords with repeated characters could be miscounted if sets are not used. Using sets ensures that duplicates do not affect the score.

All character types missing: Although the input always contains allowed characters, if a certain type is absent, the code correctly skips it, contributing 0 to the strength, avoiding overcounting. This is important for strings containing only one or two types.