420. Strong Password Checker

HardGreedyStringHeap (Priority Queue)
Leetcode Link

Problem Description

A password is considered to be strong if it satisfies the following criteria:

  1. It is between 6 to 20 characters in length.
  2. It includes at least one lowercase letter, one uppercase letter, and one digit.
  3. It doesn't contain three identical characters in a row (e.g., "aaa" is not allowed).

The task is to find the minimum number of steps required to transform the given password into a strong password according to the criteria mentioned above. If the password is already strong, the required steps will be 0. A single step could be one of the following actions:

  • Inserting one character into the password.
  • Deleting one character from the password.
  • Replacing one character in the password with another character.

Intuition

To solve this problem, we need to address three main issues related to the password:

  1. Length of the password: If it's too short, we must add characters. If it's too long, we may need to remove or replace characters.
  2. The variety of character types: We must ensure the password contains at least one lowercase letter, one uppercase letter, and one digit.
  3. Sequential characters: We have to break up any sequence of three identical characters.

When the password length is less than 6, the minimum steps required would be adding characters to reach a length of 6. The number of steps should be the greater of two values - the characters needed to reach a length of 6 or the different types of characters required for a strong password (determined by 3 - types).

For passwords of an appropriate length (6-20 characters), we focus on character variety and breaking sequences of three identical characters. The number of steps required is the greater of the number of replacements needed to break sequences or the number of character types needed to fulfill the strong password condition.

For passwords over 20 characters, the algorithm becomes more complex. We need to count the number of replacements required to fix sequences and carefully remove characters in a way that minimizes the number of replacements needed. This involves checking for sequences with lengths that are multiples of three and sequences that extend beyond three characters, as removing characters from such sequences can reduce the number of replacements needed more efficiently.

The final answer is computed based on a comparison between the number of replacements and characters needed to satisfy the strong password variety criteria, with additional steps for the extra characters that need to be removed in long passwords.

The function strongPasswordChecker implements this logic step by step, following the rules outlined above to find the minimum number of steps required.

Learn more about Greedy and Heap (Priority Queue) patterns.

Solution Approach

The provided solution in Python addresses the strong password problem by implementing a function strongPasswordChecker, which performs different operations based on the length of the password. Below we outline the approach taken by the algorithm for different password length categories:

  • Short Passwords (less than 6 characters): The solution first identifies the password is below the minimum required length, it then determines how many characters are missing to meet the length requirement. Since we might also be missing different types of characters (lowercase, uppercase, digits), we take the maximum number of missing characters or missing types because we may be able to take care of both issues with the right additions.

  • Adequate Length Passwords (between 6 and 20 characters): The solution for passwords within the acceptable length is more straightforward. It scans the password to find sequences of three or more identical characters that need to be broken up. This is accomplished by counting sequences (cnt // 3 gives us the replacements needed for each sequence). The result is the higher of the number of sequences to be replaced or the number of character types missing.

  • Long Passwords (more than 20 characters): For passwords exceeding the length limit, we implement a more complex approach. We need to reduce the length and fix the sequences simultaneously. This approach prioritizes removing characters from sequences that are just three characters long or have a remaining size of three after a multistep removal (e.g., deleting one character from a sequence of five like "aaaaa" results in "aaaa", which will still require replacement). The algorithm uses removal actions as efficiently as possible to minimize the number of needed replacements. This includes:

    • Removing characters from sequences where cnt % 3 == 0 first, as it reduces the replacements needed with just one removal.
    • Utilizing two removals for sequences where cnt % 3 == 2 because it will leave a sequence that doesn't require replacement.
    • Making three removals for the remaining sequences where cnt % 3 == 1 or non-multiples of three, as this is the least efficient but still needed.

Finally, after handling the removals, we compute the total steps as the sum of characters over the limit plus the maximum between the remaining replacements (after removals) and the types of characters we still need to add.

The data structures and patterns used in the solution include simple for-loops for iterating over characters, arithmetic operations for the calculation of sequence replacements, and conditional checks to ensure we are applying the correct logic based on the type and count of sequences.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with a small example where the password is aA123. This password is one character short of the minimum length of 6 characters. We need to check if the password satisfies the other two criteria for being strong, which is having at least one lowercase, one uppercase letter, and one digit. This example password does satisfy all character variety criteria, but it's still not strong due to its length.

Here is the step-by-step process the strongPasswordChecker function would follow for this example:

  1. Identify the Password Length Issue: The password length is 5, which is less than the required 6 characters. We identify that it's 1 character short.

  2. Character Variety Requirement: The password already contains at least one lowercase letter (a), one uppercase letter (A), and one digit (123). Hence it satisfies the character variety criteria. The categories missing would be 0 in this case.

  3. Identifying Sequential Characters: There are no sequences with three identical characters in a row, so no replacements are needed in this case.

  4. Calculating Minimum Steps for Length: Since the password is below 6 characters, the steps to reach the required length would be 6 - current length = 6 - 5 = 1. However, we already meet the criteria for character variety, so we do not need additional steps for that.

  5. Final Calculation of Steps: We take the maximum value between the steps needed for length and character variety, which is max(1, 0) = 1. Therefore, only one additional step is required.

The solution is to add one more character to this password; it does not matter what character is added, as all character variety requirements are met. After this single insertion, the password would become strong according to the problem criteria.

Solution Implementation

1class Solution:
2    def strongPasswordChecker(self, password: str) -> int:
3        # Helper function to count the number of character types in the password
4        def count_char_types(s):
5            has_lower = has_upper = has_digit = 0
6            for char in s:
7                if char.islower():
8                    has_lower = 1
9                elif char.isupper():
10                    has_upper = 1
11                elif char.isdigit():
12                    has_digit = 1
13            return has_lower + has_upper + has_digit
14
15        # Initial character type count
16        char_types = count_char_types(password)
17
18        # Password length
19        length = len(password)
20
21        # Scenarios handling based on password length
22        if length < 6:
23            # If the password is too short, it requires at least 6 characters,
24            # but also needs to address the missing character types.
25            return max(6 - length, 3 - char_types)
26        if length <= 20:
27            replace = consecutive = 0
28            previous = '~'
29            for current in password:
30                if current == previous:
31                    consecutive += 1
32                else:
33                    replace += consecutive // 3
34                    consecutive = 1
35                    previous = current
36            replace += consecutive // 3
37            return max(replace, 3 - char_types)
38
39        # If password is too long, start removing characters
40        replace = consecutive = 0
41        remove = to_remove_2 = length - 20
42        previous = '~'
43        for current in password:
44            if current == previous:
45                consecutive += 1
46            else:
47                if remove > 0 and consecutive >= 3:
48                    if consecutive % 3 == 0:
49                        remove -= 1
50                        replace -= 1
51                    elif consecutive % 3 == 1:
52                        to_remove_2 += 1
53                replace += consecutive // 3
54                consecutive = 1
55                previous = current
56
57        if remove > 0 and consecutive >= 3:
58            if consecutive % 3 == 0:
59                remove -= 1
60                replace -= 1
61            elif consecutive % 3 == 1:
62                to_remove_2 += 1
63        replace += consecutive // 3
64
65        # Optimize by merging removals with replacements
66        use_of_2 = min(replace, to_remove_2, remove // 2)
67        replace -= use_of_2
68        remove -= use_of_2 * 2
69
70        use_of_3 = min(replace, remove // 3)
71        replace -= use_of_3
72        remove -= use_of_3 * 3
73
74        # Return steps to make the password valid, which includes characters to remove
75        # and addressing the minimum number of character types (3) required.
76        return length - 20 + max(replace, 3 - char_types)
77
1class Solution {
2    public int strongPasswordChecker(String password) {
3        // Count the number of character types (lowercase, uppercase, digits) the password has.
4        int numberOfTypes = countCharacterTypes(password);
5        int passwordLength = password.length();
6        // If the password length is less than 6, return the maximum of
7        // characters needed to reach 6 or character types needed to reach 3.
8        if (passwordLength < 6) {
9            return Math.max(6 - passwordLength, 3 - numberOfTypes);
10        }
11
12        // Convert string to character array for processing.
13        char[] charArray = password.toCharArray();
14        if (passwordLength <= 20) {
15            int replaceCount = 0;
16            int consecutiveCharCount = 0;
17            char previousChar = '~'; // Initialize with a character not allowed in the password
18
19            // Iterate through the characters of the password
20            for (char currentChar : charArray) {
21                if (currentChar == previousChar) {
22                    consecutiveCharCount++;
23                } else {
24                    replaceCount += consecutiveCharCount / 3; // Each 3 consecutive characters need one replacement
25                    consecutiveCharCount = 1; // Reset count for new character
26                    previousChar = currentChar; // Set the new character as previous for next iteration
27                }
28            }
29            replaceCount += consecutiveCharCount / 3; // Add the replacements needed for the last sequence of characters
30            return Math.max(replaceCount, 3 - numberOfTypes);
31        }
32
33        // For passwords that are too long, we need to calculate replacements and removals.
34        int replaceCount = 0, removalsNeeded = passwordLength - 20;
35        int removalsForThreeConsecutive = 0; // To track removals when we have 3 consecutive characters
36        int consecutiveCharCount = 0;
37        char previousChar = '~';
38
39        for (char currentChar : charArray) {
40            if (currentChar == previousChar) {
41                consecutiveCharCount++;
42            } else {
43                if (removalsNeeded > 0 && consecutiveCharCount >= 3) {
44                    if (consecutiveCharCount % 3 == 0) {
45                        // If the count is a multiple of 3, one removal reduces one replacement needed.
46                        removalsNeeded--;
47                        replaceCount--;
48                    } else if (consecutiveCharCount % 3 == 1) {
49                        // Track the sequence with (3k+1) length
50                        removalsForThreeConsecutive++;
51                    }
52                }
53                replaceCount += consecutiveCharCount / 3;
54                consecutiveCharCount = 1; // Reset count for new character
55                previousChar = currentChar;
56            }
57        }
58        // Repeat for the last sequence of repeated characters
59        if (removalsNeeded > 0 && consecutiveCharCount >= 3) {
60            if (consecutiveCharCount % 3 == 0) {
61                removalsNeeded--;
62                replaceCount--;
63            } else if (consecutiveCharCount % 3 == 1) {
64                removalsForThreeConsecutive++;
65            }
66        }
67        replaceCount += consecutiveCharCount / 3;
68
69        // Apply the removals for sequences with (3k+2) length
70        int usedRemovalsForThreeConsecutive = Math.min(Math.min(replaceCount, removalsForThreeConsecutive), removalsNeeded / 2);
71        replaceCount -= usedRemovalsForThreeConsecutive;
72        removalsNeeded -= usedRemovalsForThreeConsecutive * 2;
73
74        // Apply the removals for sequences with (3k) length
75        int usedRemovalsForOddConsecutive = Math.min(replaceCount, removalsNeeded / 3);
76        replaceCount -= usedRemovalsForOddConsecutive;
77        removalsNeeded -= usedRemovalsForOddConsecutive * 3;
78
79        // Return the sum of excess characters removed plus the maximum of replacements needed and character types needed.
80        return (passwordLength - 20) + Math.max(replaceCount, 3 - numberOfTypes);
81    }
82
83    // Helper method to count the different types of characters in the password
84    private int countCharacterTypes(String password) {
85        int lowercaseCount = 0, uppercaseCount = 0, digitCount = 0;
86        for (char character : password.toCharArray()) {
87            if (Character.isLowerCase(character)) {
88                lowercaseCount = 1;
89            } else if (Character.isUpperCase(character)) {
90                uppercaseCount = 1;
91            } else if (Character.isDigit(character)) {
92                digitCount = 1;
93            }
94        }
95        // Returns the sum of character types present (lowercase, uppercase, digit)
96        return lowercaseCount + uppercaseCount + digitCount;
97    }
98}
99
1class Solution {
2public:
3    int strongPasswordChecker(string password) {
4        int typeCount = countCharacterTypes(password); // Count the types of characters present
5        int length = password.size(); // Get the length of the current password
6      
7        // Case when the length of the password is less than 6
8        if (length < 6) {
9            // Need to add more characters to reach 6 and ensure all character types are present
10            return max(6 - length, 3 - typeCount); 
11        }
12
13        if (length <= 20) {
14            int replacementsNeeded = 0;
15            int sequenceLength = 0;
16            char prevChar = '~'; // Initialize with a character not allowed in the password
17          
18            // Iterate over the password to find sequences of the same character
19            for (char& currChar : password) {
20                if (currChar == prevChar) {
21                    ++sequenceLength;
22                } else {
23                    // For each sequence of more than 2 identical characters,
24                    // one replacement is needed for every 3 characters
25                    replacementsNeeded += sequenceLength / 3;
26                    sequenceLength = 1;
27                    prevChar = currChar;
28                }
29            }
30            // Check replacement for the last sequence
31            replacementsNeeded += sequenceLength / 3;
32            // Ensure at least one of each character type is present
33            return max(replacementsNeeded, 3 - typeCount);
34        }
35
36        int replace = 0;
37        int toRemove = length - 20;
38        int removeTwoSequence = 0;
39        int sequenceLength = 0;
40        char prevChar = '~'; // Initialize with a character not allowed in the password
41      
42        // Iterate over the password, starting from determining 
43        // the number of deletions and replacements needed
44        for (char& currChar : password) {
45            if (currChar == prevChar) {
46                ++sequenceLength;
47            } else {
48                if (toRemove > 0 && sequenceLength >= 3) {
49                    if (sequenceLength % 3 == 0) {
50                        // Remove one and decrease one replacement when there's
51                        // a sequence whose length modulo 3 is 0
52                        --toRemove;
53                        --replace;
54                    } else if (sequenceLength % 3 == 1) {
55                        removeTwoSequence++;
56                    }
57                }
58                replace += sequenceLength / 3;
59                sequenceLength = 1;
60                prevChar = currChar;
61            }
62        }
63        // Check removal and replacement for the last sequence
64        if (toRemove > 0 && sequenceLength >= 3) {
65            if (sequenceLength % 3 == 0) {
66                --toRemove;
67                --replace;
68            } else if (sequenceLength % 3 == 1) {
69                removeTwoSequence++;
70            }
71        }
72        replace += sequenceLength / 3;
73
74        int useTwoSequenceRemovals = min(min(replace, removeTwoSequence), toRemove / 2);
75        replace -= useTwoSequenceRemovals;
76        toRemove -= useTwoSequenceRemovals * 2;
77
78        int useThreeSequenceRemovals = min(replace, toRemove / 3);
79        replace -= useThreeSequenceRemovals;
80        toRemove -= useThreeSequenceRemovals * 3;
81
82        // Sum the total actions needed to be taken to modify the password
83        // In the case of too long password: reduce the size to 20, replace if needed, and ensure all character types are present
84        return (length - 20) + max(replace, 3 - typeCount);
85    }
86
87    // Function to count the distinct character types present in the password
88    int countCharacterTypes(const string& s) {
89        int lower = 0, upper = 0, digit = 0;
90        for (const char& ch : s) {
91            if (islower(ch)) lower = 1; // Lowercase character
92            else if (isupper(ch)) upper = 1; // Uppercase character
93            else if (isdigit(ch)) digit = 1; // Digit character
94        }
95        // Sum of different types of characters present, can be 0, 1, 2 or 3
96        return lower + upper + digit;
97    }
98};
99
1// Function to count the distinct character types present in the password
2function countCharacterTypes(password: string): number {
3    let lower = 0, upper = 0, digit = 0;
4    for (const ch of password) {
5        if (isLowerCase(ch)) lower = 1; // Lowercase character
6        else if (isUpperCase(ch)) upper = 1; // Uppercase character
7        else if (isDigit(ch)) digit = 1; // Digit character
8    }
9    // Sum of different types of characters present, can be 0, 1, 2, or 3
10    return lower + upper + digit;
11}
12
13// Function to check the strength of a password
14function strongPasswordChecker(password: string): number {
15    let typeCount = countCharacterTypes(password); // Count the types of characters present
16    let length = password.length; // Get the length of the current password
17  
18    // Case when the length of the password is less than 6
19    if (length < 6) {
20        // Need to add more characters to reach 6 and ensure all character types are present
21        return Math.max(6 - length, 3 - typeCount); 
22    }
23
24    if (length <= 20) {
25        let replacementsNeeded = 0;
26        let sequenceLength = 0;
27        let prevChar = '~'; // Initialize with a character not allowed in the password
28      
29        // Iterate over the password to find sequences of the same character
30        for (const currChar of password) {
31            if (currChar === prevChar) {
32                sequenceLength++;
33            } else {
34                // For each sequence of more than 2 identical characters,
35                // one replacement is needed for every 3 characters
36                replacementsNeeded += Math.floor(sequenceLength / 3);
37                sequenceLength = 1;
38                prevChar = currChar;
39            }
40        }
41        // Check replacement for the last sequence
42        replacementsNeeded += Math.floor(sequenceLength / 3);
43        // Ensure at least one of each character type is present
44        return Math.max(replacementsNeeded, 3 - typeCount);
45    }
46
47    let replace = 0;
48    let toRemove = length - 20;
49    let removeTwoSequence = 0;
50    let sequenceLength = 0;
51    let prevChar = '~'; // Initialize with a character not allowed in the password
52  
53    // Iterate over the password, starting from determining the number of deletions and replacements needed
54    for (const currChar of password) {
55        if (currChar === prevChar) {
56            sequenceLength++;
57        } else {
58            if (toRemove > 0 && sequenceLength >= 3) {
59                if (sequenceLength % 3 === 0) {
60                    // Remove one and decrease one replacement when there's
61                    // a sequence whose length modulo 3 is 0
62                    toRemove--;
63                    replace--;
64                } else if (sequenceLength % 3 === 1) {
65                    removeTwoSequence++;
66                }
67            }
68            replace += Math.floor(sequenceLength / 3);
69            sequenceLength = 1;
70            prevChar = currChar;
71        }
72    }
73    // Check removal and replacement for the last sequence
74    if (toRemove > 0 && sequenceLength >= 3) {
75        if (sequenceLength % 3 === 0) {
76            toRemove--;
77            replace--;
78        } else if (sequenceLength % 3 === 1) {
79            removeTwoSequence++;
80        }
81    }
82    replace += Math.floor(sequenceLength / 3);
83
84    let useTwoSequenceRemovals = Math.min(Math.min(replace, removeTwoSequence), Math.floor(toRemove / 2));
85    replace -= useTwoSequenceRemovals;
86    toRemove -= useTwoSequenceRemovals * 2;
87
88    let useThreeSequenceRemovals = Math.min(replace, Math.floor(toRemove / 3));
89    replace -= useThreeSequenceRemovals;
90    toRemove -= useThreeSequenceRemovals * 3;
91
92    // Sum the total actions needed to be taken to modify the password
93    // In the case of a too long password: reduce the size to 20, replace if needed, and ensure all character types are present
94    return (length - 20) + Math.max(replace, 3 - typeCount);
95}
96
97// Utility function to check if a character is a lowercase letter
98function isLowerCase(char: string): boolean {
99    return /^[a-z]$/.test(char);
100}
101
102// Utility function to check if a character is an uppercase letter
103function isUpperCase(char: string): boolean {
104    return /^[A-Z]$/.test(char);
105}
106
107// Utility function to check if a character is a digit
108function isDigit(char: string): boolean {
109    return /^\d$/.test(char);
110}
111

Time and Space Complexity

Time Complexity

The time complexity of the given strongPasswordChecker function can be analyzed as follows:

  • The function begins by checking the password for character types to ensure it includes a mix of lowercase letters, uppercase letters, and digits. This check is performed in linear time relative to the password's length n. Therefore, its time complexity is O(n).

  • If the password length n is less than 6, the function returns the maximum of 6 - n and 3 - types. This is a constant time operation, so O(1).

  • For passwords whose length is between 6 and 20 inclusive, the function then enters a loop that iterates over each character of the password to count consecutive characters and calculates how many changes are needed. This loop runs in linear time O(n) because it goes through each character once.

  • For passwords longer than 20 characters, the function continues with additional loops and calculations. It involves more complex steps for deleting extra characters to reduce the password length to 20, replacing characters to avoid three consecutive identical characters, and balancing the number of deletions of one, two, or three characters. Despite additional steps, these are also performed in a linear pass, resulting in a time complexity of O(n).

  • The subsequent operations after the for-loops are constant-time arithmetic operations, which do not change the overall time complexity.

Due to the linear scans of the input, regardless of the case, the overall time complexity is O(n) where n is the length of the password string.

Space Complexity

The space complexity of the function is also quite straightforward:

  • Counters and variables to keep track of conditions and operations within the password do not grow with n but are a fixed set. This requires O(1) space.

  • The input password string itself uses O(n) space which is given as input, so we consider the additional space used by the algorithm, which is constant.

  • The function does not use any additional data structures that scale with the size of the input.

Therefore, the overall space complexity of the strongPasswordChecker function is O(1).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?

Recommended Readings

Greedy Introduction

Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More