#420

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Strong Password Checker

The Strong Password Checker problem challenges you to optimize password strength while minimizing steps using greedy algorithms and invariant validation.

string greedy heap priority queue

Problem Statement

You are given a string password and need to determine the minimum number of steps required to make it strong. A password is considered strong if it meets the following conditions:

It must be at least 6 characters long and at most 20 characters. 2. It must contain at least one lowercase letter, one uppercase letter, and one digit. 3. It must not contain three consecutive repeating characters (e.g., 'aaa'). Return the minimum number of steps to achieve a strong password, or 0 if the password is already strong.

Examples

Example 1

Input: password = "a"

Output: 5

Example details omitted.

Example 2

Input: password = "aA1"

Output: 3

Example details omitted.

Example 3

Input: password = "1337C0d3"

Output: 0

Example details omitted.

Constraints

1 <= password.length <= 50
password consists of letters, digits, dot '.' or exclamation mark '!'.

Solution Approach

Greedy Approach for Length Constraints

The first step is to check the length of the password. If it is less than 6 characters, we need to add characters until the length requirement is satisfied. If the password exceeds 20 characters, we must delete characters to bring it within the limit. The greedy approach ensures the minimum number of additions or deletions by directly adjusting the length.

Invariant Validation for Character Types

The second step is to ensure the password contains at least one lowercase letter, one uppercase letter, and one digit. If any of these character types is missing, we must add the corresponding character type. This is another greedy choice since adding the missing characters will make the password strong with the least steps.

Handling Consecutive Repeating Characters

The third step is to handle consecutive repeating characters. If a sequence of three or more repeating characters is found, we need to modify the password by either deleting or changing some of those characters. This part of the solution is important to avoid violating the password's strength requirement.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) due to a single pass required to check and modify the password, where n is the length of the string. The space complexity is O(1) since we only need a few variables to track character types and consecutive characters, with no additional data structures.

What Interviewers Usually Probe

Look for the candidate’s understanding of greedy algorithms and the ability to identify the most efficient solution to achieve password strength.
Check if the candidate handles edge cases, such as passwords already strong, too short, or containing invalid characters.
Evaluate how the candidate approaches the problem using invariant validation while considering each password condition separately.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle edge cases, such as passwords shorter than 6 characters or those that already meet all conditions.
Incorrectly applying character type checks, which may lead to unnecessary changes or missed modifications.
Not considering efficient handling of consecutive repeating characters, which could lead to unnecessary deletions or changes.

Follow-up variants

Different constraints could be introduced, such as requiring a password to contain special characters, changing the acceptable length range, or adding more character type checks.
Handling passwords with non-alphanumeric characters like punctuation marks could be an additional challenge, testing edge case handling.
The problem could be modified to handle passwords that must meet different password strength levels, introducing more complex validation conditions.

FAQ

What is the primary pattern used in the Strong Password Checker problem?

The primary pattern is greedy choice plus invariant validation, where the goal is to minimize steps while ensuring each password condition is satisfied.

How can I optimize my solution to handle large passwords efficiently?

By ensuring that your solution has linear time complexity, you can handle passwords up to the maximum length without unnecessary processing or overhead.

What happens if the password is already strong?

If the password is already strong, no changes are necessary, and the output should be 0 steps.

What is the best way to handle consecutive repeating characters?

The best way is to modify the password by either deleting or changing characters to avoid three consecutive repeats, ensuring a valid password.

Are there any constraints on the types of characters in the password?

Yes, the password can consist of lowercase and uppercase letters, digits, as well as the characters '.' and '!', which must be handled accordingly.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        def countTypes(s):
            a = b = c = 0
            for ch in s:
                if ch.islower():
                    a = 1
                elif ch.isupper():
                    b = 1
                elif ch.isdigit():
                    c = 1
            return a + b + c

        types = countTypes(password)
        n = len(password)
        if n < 6:
            return max(6 - n, 3 - types)
        if n <= 20:
            replace = cnt = 0
            prev = '~'
            for curr in password:
                if curr == prev:
                    cnt += 1
                else:
                    replace += cnt // 3
                    cnt = 1
                    prev = curr
            replace += cnt // 3
            return max(replace, 3 - types)
        replace = cnt = 0
        remove, remove2 = n - 20, 0
        prev = '~'
        for curr in password:
            if curr == prev:
                cnt += 1
            else:
                if remove > 0 and cnt >= 3:
                    if cnt % 3 == 0:
                        remove -= 1
                        replace -= 1
                    elif cnt % 3 == 1:
                        remove2 += 1
                replace += cnt // 3
                cnt = 1
                prev = curr
        if remove > 0 and cnt >= 3:
            if cnt % 3 == 0:
                remove -= 1
                replace -= 1
            elif cnt % 3 == 1:
                remove2 += 1
        replace += cnt // 3
        use2 = min(replace, remove2, remove // 2)
        replace -= use2
        remove -= use2 * 2

        use3 = min(replace, remove // 3)
        replace -= use3
        remove -= use3 * 3
        return n - 20 + max(replace, 3 - types)

Continue Practicing

#767 reorganize string #1405 longest happy string #409 longest palindrome