420. Strong Password Checker
Problem Description
A password is considered to be strong if it satisfies the following criteria:
- It is between 6 to 20 characters in length.
- It includes at least one lowercase letter, one uppercase letter, and one digit.
- 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:
- 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.
- The variety of character types: We must ensure the password contains at least one lowercase letter, one uppercase letter, and one digit.
- 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.
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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 // 3gives 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 == 0first, as it reduces the replacements needed with just one removal. - Utilizing two removals for sequences where
cnt % 3 == 2because it will leave a sequence that doesn't require replacement. - Making three removals for the remaining sequences where
cnt % 3 == 1or non-multiples of three, as this is the least efficient but still needed.
- Removing characters from sequences where
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.
Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?
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:
-
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.
-
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. -
Identifying Sequential Characters: There are no sequences with three identical characters in a row, so no replacements are needed in this case.
-
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. -
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)
771class 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}
991class 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};
991// 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}
111What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Time 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 isO(n). -
If the password length
nis less than 6, the function returns the maximum of6 - nand3 - types. This is a constant time operation, soO(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
nbut are a fixed set. This requiresO(1)space. -
The input
passwordstring itself usesO(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.
Depth first search can be used to find whether two components in a graph are connected.
Recommended Readings
Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
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
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.