Facebook Pixel

420. Strong Password Checker

HardGreedyStringHeap (Priority Queue)
Leetcode Link

Problem Description

This problem asks you to determine the minimum number of operations needed to make a password strong. A strong password must satisfy three conditions:

  1. Length requirement: The password must have between 6 and 20 characters (inclusive)
  2. Character type requirement: The password must contain at least one lowercase letter, one uppercase letter, and one digit
  3. No triple repetition: The password cannot have three identical characters in a row (e.g., "aaa" is not allowed)

You can perform three types of operations, each counting as one step:

  • Insert: Add one character at any position
  • Delete: Remove one character from any position
  • Replace: Change one character to a different character

The challenge is to find the minimum number of operations needed based on the password's current state:

  • If the password is too short (less than 6 characters): You'll need to insert characters. These insertions can also help satisfy missing character types.

  • If the password has acceptable length (6-20 characters): Focus on fixing any triple repetitions and ensuring all three character types are present. Replacements are often the most efficient operation here.

  • If the password is too long (more than 20 characters): You must delete excess characters. The strategy becomes complex because deletions can also help break up triple repetitions efficiently. The solution needs to carefully balance deletions with replacements to minimize total operations.

The algorithm must handle the interplay between these requirements. For example, replacing a character in a sequence of repeated characters can both break up the repetition and add a missing character type, accomplishing two goals with one operation.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is to handle the problem differently based on the password length, as each scenario has distinct optimal strategies.

For passwords shorter than 6 characters: We must add characters to reach the minimum length. Since we're already adding characters, we can strategically choose what to add to satisfy the character type requirements. The answer is simply max(6 - n, 3 - types) because we need at least 6 - n insertions for length, and at least 3 - types operations to get all required character types. These goals can overlap when we insert missing character types.

For passwords with length 6-20: Length is acceptable, so we focus on fixing repetitions and character types. When we encounter sequences of 3+ identical characters, we need to break them up. A sequence of length k requires k // 3 replacements to fix (e.g., "aaaaa" needs 1 replacement to become "aaXaa", and "aaaaaa" needs 2 replacements). Replacements are perfect here because one replacement can both break a repetition AND add a missing character type. The answer is max(replace, 3 - types) since replacements can serve double duty.

For passwords longer than 20 characters: This is the most complex case. We must delete characters, but deletions interact cleverly with repetitions. Consider "aaa" - normally this needs 1 replacement. But if we delete one character to get "aa", no replacement is needed! This creates an optimization opportunity.

The crucial observation is that sequences of repeated characters have different deletion efficiencies based on their length modulo 3:

  • Length 3k (e.g., "aaa", "aaaaaa"): Deleting 1 character saves 1 replacement
  • Length 3k + 1 (e.g., "aaaa"): Deleting 2 characters saves 1 replacement
  • Length 3k + 2 (e.g., "aaaaa"): Deleting 3 characters saves 1 replacement

The algorithm prioritizes deletions in order of efficiency: first handle 3k sequences (1 deletion per saved replacement), then 3k + 1 sequences (2 deletions per saved replacement), and finally 3k + 2 sequences (3 deletions per saved replacement). After using deletions optimally to reduce required replacements, we still need to ensure we have all character types, leading to the formula n - 20 + max(replace, 3 - types).

Solution Approach

The implementation divides the problem into three cases based on password length, with a helper function to count character types.

Helper Function - Counting Character Types:

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

This function returns how many of the three required character types are present (0-3).

Case 1: Length < 6

if n < 6:
    return max(6 - n, 3 - types)

We need 6 - n insertions to reach minimum length and 3 - types operations to get all character types. Since insertions can add missing types, we take the maximum.

Case 2: Length 6-20

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)

We scan through the password tracking consecutive identical characters. When the character changes or we reach the end, we calculate replacements needed: cnt // 3. For example, "aaaaa" (cnt=5) needs 5//3 = 1 replacement. The final answer is the maximum of total replacements needed and missing character types.

Case 3: Length > 20

replace = cnt = 0
remove, remove2 = n - 20, 0
prev = '~'

We need to remove n - 20 characters. The algorithm tracks:

  • remove: remaining deletions available
  • remove2: count of sequences with length 3k + 1
  • replace: replacements still needed after optimal deletions

First pass - handle sequences and optimize 3k length sequences:

for curr in password:
    if curr == prev:
        cnt += 1
    else:
        if remove > 0 and cnt >= 3:
            if cnt % 3 == 0:  # Length 3k - most efficient
                remove -= 1
                replace -= 1
            elif cnt % 3 == 1:  # Length 3k+1 - track for later
                remove2 += 1
        replace += cnt // 3
        cnt = 1
        prev = curr

Second pass - use remaining deletions optimally:

use2 = min(replace, remove2, remove // 2)  # Handle 3k+1 sequences
replace -= use2
remove -= use2 * 2

use3 = min(replace, remove // 3)  # Handle 3k+2 sequences
replace -= use3
remove -= use3 * 3

The algorithm prioritizes:

  1. Delete 1 character from 3k sequences (1 deletion saves 1 replacement)
  2. Delete 2 characters from 3k+1 sequences (2 deletions save 1 replacement)
  3. Delete 3 characters from 3k+2 sequences (3 deletions save 1 replacement)

Finally, return n - 20 + max(replace, 3 - types), which represents:

  • n - 20: mandatory deletions
  • max(replace, 3 - types): additional operations needed for repetitions and character types

This greedy approach ensures we use deletions as efficiently as possible to minimize total operations.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through a concrete example: password = "aaaaAAA1234567890123"

Step 1: Initial Analysis

  • Length: 20 characters (valid range, no insertions or deletions needed)
  • Character types: lowercase 'a', uppercase 'A', digit '1' - all 3 types present ✓
  • Repetitions: "aaaa" (4 consecutive) and "AAA" (3 consecutive)

Step 2: Count Required Replacements We scan through the password tracking consecutive identical characters:

  • "aaaa" has length 4, needs 4 // 3 = 1 replacement
  • "AAA" has length 3, needs 3 // 3 = 1 replacement
  • Total replacements needed: 2

Step 3: Calculate Final Answer Since we're in the 6-20 length range:

  • Replacements needed: 2
  • Missing character types: 0 (we have all 3)
  • Answer: max(2, 0) = 2

The Fix: We could change the password to "aaXaAAX1234567890123" with 2 replacements.

Now let's see a more complex example: password = "aaaaaaaa" (8 'a's)

Step 1: Initial Analysis

  • Length: 8 characters (valid range)
  • Character types: only lowercase - missing uppercase and digit (need 2 more types)
  • Repetitions: "aaaaaaaa" (8 consecutive)

Step 2: Count Required Replacements

  • "aaaaaaaa" has length 8, needs 8 // 3 = 2 replacements

Step 3: Calculate Final Answer

  • Replacements needed: 2
  • Missing character types: 2 (need uppercase and digit)
  • Answer: max(2, 2) = 2

The Fix: We could change to "aaAaa1aa" - the 2 replacements both break repetitions AND add missing character types, achieving both goals simultaneously!

Finally, a deletion example: password = "aaaaaaaaaaaaaaaaaaaaa" (21 'a's)

Step 1: Initial Analysis

  • Length: 21 characters (too long, need to delete 1)
  • Character types: only lowercase - missing 2 types
  • Repetitions: 21 consecutive 'a's

Step 2: Apply Deletion Strategy

  • Without any optimization: 21 'a's would need 21 // 3 = 7 replacements
  • We must delete 1 character (21 - 20 = 1)
  • Length 21 = 3×7, so this is a 3k length sequence
  • Deleting 1 character gives us 20 'a's, which needs 20 // 3 = 6 replacements
  • We saved 1 replacement with 1 deletion!

Step 3: Calculate Final Answer

  • Mandatory deletions: 1
  • Replacements still needed after deletion: 6
  • Missing character types: 2
  • Answer: 1 + max(6, 2) = 1 + 6 = 7

The Fix: Delete one 'a' to get 20 characters, then make 6 replacements to break repetitions and add missing types.

Solution Implementation

1class Solution:
2    def strongPasswordChecker(self, password: str) -> int:
3        def count_character_types(s: str) -> int:
4            """
5            Count how many character types (lowercase, uppercase, digit) are present.
6            Returns a number between 0 and 3.
7            """
8            has_lower = has_upper = has_digit = 0
9          
10            for char in s:
11                if char.islower():
12                    has_lower = 1
13                elif char.isupper():
14                    has_upper = 1
15                elif char.isdigit():
16                    has_digit = 1
17          
18            return has_lower + has_upper + has_digit
19      
20        # Count existing character types and get password length
21        existing_types = count_character_types(password)
22        password_length = len(password)
23      
24        # Case 1: Password is too short (less than 6 characters)
25        if password_length < 6:
26            # Need to add characters to reach 6, and ensure we have all 3 types
27            chars_to_add = 6 - password_length
28            types_to_add = 3 - existing_types
29            return max(chars_to_add, types_to_add)
30      
31        # Case 2: Password length is acceptable (6-20 characters)
32        if password_length <= 20:
33            # Count replacements needed to break sequences of 3+ repeating characters
34            replacements_needed = 0
35            consecutive_count = 1
36            previous_char = '~'  # Use a non-password character as initial value
37          
38            for current_char in password:
39                if current_char == previous_char:
40                    consecutive_count += 1
41                else:
42                    # For every 3 consecutive chars, we need 1 replacement
43                    replacements_needed += consecutive_count // 3
44                    consecutive_count = 1
45                    previous_char = current_char
46          
47            # Don't forget the last sequence
48            replacements_needed += consecutive_count // 3
49          
50            # Need to fix both repeating sequences and missing character types
51            types_to_add = 3 - existing_types
52            return max(replacements_needed, types_to_add)
53      
54        # Case 3: Password is too long (more than 20 characters)
55        # Strategy: Remove excess characters optimally to minimize replacements
56      
57        replacements_needed = 0
58        consecutive_count = 1
59        chars_to_remove = password_length - 20
60      
61        # Track sequences with remainder 1 when divided by 3
62        # These are priority for using 2-char removals
63        sequences_with_remainder_1 = 0
64      
65        previous_char = '~'
66      
67        for current_char in password:
68            if current_char == previous_char:
69                consecutive_count += 1
70            else:
71                if chars_to_remove > 0 and consecutive_count >= 3:
72                    # Sequences divisible by 3: removing 1 char saves 1 replacement
73                    if consecutive_count % 3 == 0:
74                        chars_to_remove -= 1
75                        replacements_needed -= 1
76                    # Sequences with remainder 1: good candidates for 2-char removal
77                    elif consecutive_count % 3 == 1:
78                        sequences_with_remainder_1 += 1
79              
80                replacements_needed += consecutive_count // 3
81                consecutive_count = 1
82                previous_char = current_char
83      
84        # Process the last sequence
85        if chars_to_remove > 0 and consecutive_count >= 3:
86            if consecutive_count % 3 == 0:
87                chars_to_remove -= 1
88                replacements_needed -= 1
89            elif consecutive_count % 3 == 1:
90                sequences_with_remainder_1 += 1
91      
92        replacements_needed += consecutive_count // 3
93      
94        # Use remaining removals optimally
95        # Priority 1: Remove 2 chars from sequences with remainder 1
96        two_char_removals = min(replacements_needed, sequences_with_remainder_1, chars_to_remove // 2)
97        replacements_needed -= two_char_removals
98        chars_to_remove -= two_char_removals * 2
99      
100        # Priority 2: Remove 3 chars to eliminate entire replacement needs
101        three_char_removals = min(replacements_needed, chars_to_remove // 3)
102        replacements_needed -= three_char_removals
103        chars_to_remove -= three_char_removals * 3
104      
105        # Total operations = deletions + max(remaining replacements, missing types)
106        types_to_add = 3 - existing_types
107        return (password_length - 20) + max(replacements_needed, types_to_add)
108
1class Solution {
2    /**
3     * Calculates minimum number of changes needed to make a strong password.
4     * A strong password must have: length 6-20, at least one lowercase, 
5     * one uppercase, one digit, and no three repeating characters in a row.
6     * 
7     * @param password The input password string to check
8     * @return Minimum number of changes (insertions/deletions/replacements) needed
9     */
10    public int strongPasswordChecker(String password) {
11        // Count how many character types (lowercase, uppercase, digit) are present
12        int characterTypes = countTypes(password);
13        int length = password.length();
14      
15        // Case 1: Password is too short (less than 6 characters)
16        if (length < 6) {
17            // Need to add characters to reach 6, and ensure we have all 3 types
18            return Math.max(6 - length, 3 - characterTypes);
19        }
20      
21        char[] passwordChars = password.toCharArray();
22      
23        // Case 2: Password length is valid (6-20 characters)
24        if (length <= 20) {
25            int replacementsNeeded = 0;
26            int consecutiveCount = 0;
27            char previousChar = '~'; // Initialize with a character not in password
28          
29            // Count replacements needed to break sequences of 3+ repeating characters
30            for (char currentChar : passwordChars) {
31                if (currentChar == previousChar) {
32                    consecutiveCount++;
33                } else {
34                    // For every 3 consecutive chars, we need 1 replacement
35                    replacementsNeeded += consecutiveCount / 3;
36                    consecutiveCount = 1;
37                    previousChar = currentChar;
38                }
39            }
40            replacementsNeeded += consecutiveCount / 3;
41          
42            // Return max of replacements needed and missing character types
43            return Math.max(replacementsNeeded, 3 - characterTypes);
44        }
45      
46        // Case 3: Password is too long (more than 20 characters)
47        int replacementsNeeded = 0;
48        int deletionsRequired = length - 20; // Number of chars to delete
49        int sequencesWithRemainder2 = 0; // Sequences where length % 3 == 1
50        int consecutiveCount = 0;
51        char previousChar = '~';
52      
53        // Process each character to find repeating sequences
54        for (char currentChar : passwordChars) {
55            if (currentChar == previousChar) {
56                consecutiveCount++;
57            } else {
58                if (deletionsRequired > 0 && consecutiveCount >= 3) {
59                    // If sequence length % 3 == 0, deleting 1 char saves 1 replacement
60                    if (consecutiveCount % 3 == 0) {
61                        deletionsRequired--;
62                        replacementsNeeded--;
63                    } 
64                    // If sequence length % 3 == 1, track for later optimization
65                    else if (consecutiveCount % 3 == 1) {
66                        sequencesWithRemainder2++;
67                    }
68                }
69                replacementsNeeded += consecutiveCount / 3;
70                consecutiveCount = 1;
71                previousChar = currentChar;
72            }
73        }
74      
75        // Handle the last sequence
76        if (deletionsRequired > 0 && consecutiveCount >= 3) {
77            if (consecutiveCount % 3 == 0) {
78                deletionsRequired--;
79                replacementsNeeded--;
80            } else if (consecutiveCount % 3 == 1) {
81                sequencesWithRemainder2++;
82            }
83        }
84        replacementsNeeded += consecutiveCount / 3;
85      
86        // Optimize deletions to reduce replacements
87        // Use 2 deletions on sequences with remainder 2 (length % 3 == 1)
88        int use2Deletions = Math.min(Math.min(replacementsNeeded, sequencesWithRemainder2), 
89                                     deletionsRequired / 2);
90        replacementsNeeded -= use2Deletions;
91        deletionsRequired -= use2Deletions * 2;
92      
93        // Use 3 deletions on remaining sequences to reduce replacements
94        int use3Deletions = Math.min(replacementsNeeded, deletionsRequired / 3);
95        replacementsNeeded -= use3Deletions;
96        deletionsRequired -= use3Deletions * 3;
97      
98        // Total operations = deletions + max(remaining replacements, missing types)
99        return (length - 20) + Math.max(replacementsNeeded, 3 - characterTypes);
100    }
101  
102    /**
103     * Counts the number of character types present in the string.
104     * Types are: lowercase letter, uppercase letter, digit
105     * 
106     * @param s The input string to analyze
107     * @return Number of different character types (0-3)
108     */
109    private int countTypes(String s) {
110        int hasLowercase = 0;
111        int hasUppercase = 0;
112        int hasDigit = 0;
113      
114        // Check each character and mark which types are present
115        for (char ch : s.toCharArray()) {
116            if (Character.isLowerCase(ch)) {
117                hasLowercase = 1;
118            } else if (Character.isUpperCase(ch)) {
119                hasUppercase = 1;
120            } else if (Character.isDigit(ch)) {
121                hasDigit = 1;
122            }
123        }
124      
125        return hasLowercase + hasUppercase + hasDigit;
126    }
127}
128
1class Solution {
2public:
3    int strongPasswordChecker(string password) {
4        // Count how many character types are present (lowercase, uppercase, digit)
5        int typesPresent = countTypes(password);
6        int passwordLength = password.size();
7      
8        // Case 1: Password is too short (less than 6 characters)
9        if (passwordLength < 6) {
10            // Need to add characters to reach minimum length
11            // Also need to ensure we have all 3 character types
12            return max(6 - passwordLength, 3 - typesPresent);
13        }
14      
15        // Case 2: Password length is valid (6-20 characters)
16        if (passwordLength <= 20) {
17            // Count replacements needed to break sequences of 3+ repeated characters
18            int replacementsNeeded = 0;
19            int consecutiveCount = 0;
20            char previousChar = '~';  // Placeholder for initial comparison
21          
22            for (char& currentChar : password) {
23                if (currentChar == previousChar) {
24                    consecutiveCount++;
25                } else {
26                    // For every 3 consecutive characters, we need 1 replacement
27                    replacementsNeeded += consecutiveCount / 3;
28                    consecutiveCount = 1;
29                    previousChar = currentChar;
30                }
31            }
32            replacementsNeeded += consecutiveCount / 3;
33          
34            // Return max of replacements needed and missing character types
35            return max(replacementsNeeded, 3 - typesPresent);
36        }
37      
38        // Case 3: Password is too long (more than 20 characters)
39        int replacementsNeeded = 0;
40        int deletionsNeeded = passwordLength - 20;
41        int sequencesWithRemainder2 = 0;  // Sequences where length % 3 == 1
42        int consecutiveCount = 0;
43        char previousChar = '~';
44      
45        // First pass: identify sequences and optimize deletions
46        for (char& currentChar : password) {
47            if (currentChar == previousChar) {
48                consecutiveCount++;
49            } else {
50                if (deletionsNeeded > 0 && consecutiveCount >= 3) {
51                    // Sequences divisible by 3 can be optimized with 1 deletion
52                    if (consecutiveCount % 3 == 0) {
53                        deletionsNeeded--;
54                        replacementsNeeded--;
55                    } else if (consecutiveCount % 3 == 1) {
56                        // Track sequences with remainder 1 (need 2 deletions to optimize)
57                        sequencesWithRemainder2++;
58                    }
59                }
60                replacementsNeeded += consecutiveCount / 3;
61                consecutiveCount = 1;
62                previousChar = currentChar;
63            }
64        }
65      
66        // Handle the last sequence
67        if (deletionsNeeded > 0 && consecutiveCount >= 3) {
68            if (consecutiveCount % 3 == 0) {
69                deletionsNeeded--;
70                replacementsNeeded--;
71            } else if (consecutiveCount % 3 == 1) {
72                sequencesWithRemainder2++;
73            }
74        }
75        replacementsNeeded += consecutiveCount / 3;
76      
77        // Second optimization: use 2 deletions to reduce replacement count
78        int deletionsUsedForRemainder2 = min(min(replacementsNeeded, sequencesWithRemainder2), 
79                                              deletionsNeeded / 2);
80        replacementsNeeded -= deletionsUsedForRemainder2;
81        deletionsNeeded -= deletionsUsedForRemainder2 * 2;
82      
83        // Third optimization: use 3 deletions to reduce replacement count
84        int deletionsUsedForRemainder0 = min(replacementsNeeded, deletionsNeeded / 3);
85        replacementsNeeded -= deletionsUsedForRemainder0;
86        deletionsNeeded -= deletionsUsedForRemainder0 * 3;
87      
88        // Total operations = deletions + max(remaining replacements, missing types)
89        return (passwordLength - 20) + max(replacementsNeeded, 3 - typesPresent);
90    }
91  
92    // Helper function to count how many character types are present
93    int countTypes(string& s) {
94        int hasLowercase = 0;
95        int hasUppercase = 0;
96        int hasDigit = 0;
97      
98        for (char& ch : s) {
99            if (islower(ch)) {
100                hasLowercase = 1;
101            } else if (isupper(ch)) {
102                hasUppercase = 1;
103            } else if (isdigit(ch)) {
104                hasDigit = 1;
105            }
106        }
107      
108        return hasLowercase + hasUppercase + hasDigit;
109    }
110};
111
1/**
2 * Calculates minimum number of operations to make a strong password
3 * A strong password has: length 6-20, at least 1 lowercase, 1 uppercase, 1 digit,
4 * and no 3+ consecutive repeating characters
5 * @param password - The input password string to check
6 * @returns Minimum number of operations (insertions, deletions, or replacements)
7 */
8function strongPasswordChecker(password: string): number {
9    // Count how many character types are present (lowercase, uppercase, digit)
10    const typesPresent = countTypes(password);
11    const passwordLength = password.length;
12  
13    // Case 1: Password is too short (less than 6 characters)
14    if (passwordLength < 6) {
15        // Need to add characters to reach minimum length
16        // Also need to ensure we have all 3 character types
17        return Math.max(6 - passwordLength, 3 - typesPresent);
18    }
19  
20    // Case 2: Password length is valid (6-20 characters)
21    if (passwordLength <= 20) {
22        // Count replacements needed to break sequences of 3+ repeated characters
23        let replacementsNeeded = 0;
24        let consecutiveCount = 0;
25        let previousChar = '~';  // Placeholder for initial comparison
26      
27        for (const currentChar of password) {
28            if (currentChar === previousChar) {
29                consecutiveCount++;
30            } else {
31                // For every 3 consecutive characters, we need 1 replacement
32                replacementsNeeded += Math.floor(consecutiveCount / 3);
33                consecutiveCount = 1;
34                previousChar = currentChar;
35            }
36        }
37        replacementsNeeded += Math.floor(consecutiveCount / 3);
38      
39        // Return max of replacements needed and missing character types
40        return Math.max(replacementsNeeded, 3 - typesPresent);
41    }
42  
43    // Case 3: Password is too long (more than 20 characters)
44    let replacementsNeeded = 0;
45    let deletionsNeeded = passwordLength - 20;
46    let sequencesWithRemainder2 = 0;  // Sequences where length % 3 == 1
47    let consecutiveCount = 0;
48    let previousChar = '~';
49  
50    // First pass: identify sequences and optimize deletions
51    for (const currentChar of password) {
52        if (currentChar === previousChar) {
53            consecutiveCount++;
54        } else {
55            if (deletionsNeeded > 0 && consecutiveCount >= 3) {
56                // Sequences divisible by 3 can be optimized with 1 deletion
57                if (consecutiveCount % 3 === 0) {
58                    deletionsNeeded--;
59                    replacementsNeeded--;
60                } else if (consecutiveCount % 3 === 1) {
61                    // Track sequences with remainder 1 (need 2 deletions to optimize)
62                    sequencesWithRemainder2++;
63                }
64            }
65            replacementsNeeded += Math.floor(consecutiveCount / 3);
66            consecutiveCount = 1;
67            previousChar = currentChar;
68        }
69    }
70  
71    // Handle the last sequence
72    if (deletionsNeeded > 0 && consecutiveCount >= 3) {
73        if (consecutiveCount % 3 === 0) {
74            deletionsNeeded--;
75            replacementsNeeded--;
76        } else if (consecutiveCount % 3 === 1) {
77            sequencesWithRemainder2++;
78        }
79    }
80    replacementsNeeded += Math.floor(consecutiveCount / 3);
81  
82    // Second optimization: use 2 deletions to reduce replacement count
83    const deletionsUsedForRemainder2 = Math.min(
84        Math.min(replacementsNeeded, sequencesWithRemainder2),
85        Math.floor(deletionsNeeded / 2)
86    );
87    replacementsNeeded -= deletionsUsedForRemainder2;
88    deletionsNeeded -= deletionsUsedForRemainder2 * 2;
89  
90    // Third optimization: use 3 deletions to reduce replacement count
91    const deletionsUsedForRemainder0 = Math.min(
92        replacementsNeeded,
93        Math.floor(deletionsNeeded / 3)
94    );
95    replacementsNeeded -= deletionsUsedForRemainder0;
96    deletionsNeeded -= deletionsUsedForRemainder0 * 3;
97  
98    // Total operations = deletions + max(remaining replacements, missing types)
99    return (passwordLength - 20) + Math.max(replacementsNeeded, 3 - typesPresent);
100}
101
102/**
103 * Helper function to count how many character types are present in the password
104 * @param s - The password string to analyze
105 * @returns Number of character types present (0-3)
106 */
107function countTypes(s: string): number {
108    let hasLowercase = 0;
109    let hasUppercase = 0;
110    let hasDigit = 0;
111  
112    for (const ch of s) {
113        if (ch >= 'a' && ch <= 'z') {
114            hasLowercase = 1;
115        } else if (ch >= 'A' && ch <= 'Z') {
116            hasUppercase = 1;
117        } else if (ch >= '0' && ch <= '9') {
118            hasDigit = 1;
119        }
120    }
121  
122    return hasLowercase + hasUppercase + hasDigit;
123}
124

Time and Space Complexity

Time Complexity: O(n) where n is the length of the password string.

The algorithm makes a single pass through the password string to count character types in the countTypes function, which takes O(n) time. Then, depending on the password length:

  • If n < 6: Direct calculation in O(1)
  • If 6 <= n <= 20: One pass through the password to count consecutive characters, taking O(n)
  • If n > 20: One pass through the password to count consecutive characters and calculate removals, taking O(n)

All operations within the loops (comparisons, arithmetic operations, modulo calculations) are O(1). Therefore, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

  • Variables for counting types (a, b, c, types): O(1)
  • Variables for tracking consecutive characters and operations (replace, cnt, remove, remove2, use2, use3): O(1)
  • Variables for character comparison (prev, curr): O(1)

No additional data structures that scale with input size are used, making the space complexity O(1).

Common Pitfalls

1. Forgetting to Process the Last Sequence of Repeating Characters

One of the most common mistakes is not handling the final sequence of consecutive characters after the main loop completes. The loop only processes a sequence when it encounters a different character, but if the password ends with repeating characters, these won't be counted.

Incorrect Implementation:

for current_char in password:
    if current_char == previous_char:
        consecutive_count += 1
    else:
        replacements_needed += consecutive_count // 3
        consecutive_count = 1
        previous_char = current_char
# Missing: Final sequence is never processed!

Correct Implementation:

for current_char in password:
    if current_char == previous_char:
        consecutive_count += 1
    else:
        replacements_needed += consecutive_count // 3
        consecutive_count = 1
        previous_char = current_char

# Process the last sequence after loop ends
replacements_needed += consecutive_count // 3

2. Incorrect Initialization of Previous Character

Using an empty string or a character that could appear in the password as the initial value for previous_char can cause the first character to be incorrectly counted as part of a sequence.

Incorrect Implementation:

previous_char = ''  # Empty string causes comparison issues
# or
previous_char = 'a'  # If password starts with 'a', it's counted incorrectly

Correct Implementation:

previous_char = '~'  # Use a character that won't appear in passwords

3. Misunderstanding the Deletion Priority in Case 3

When the password is too long, not understanding why we prioritize sequences with different remainders can lead to suboptimal solutions. The algorithm must recognize that:

  • Deleting 1 char from a sequence of length 3k (remainder 0) saves 1 replacement
  • Deleting 2 chars from a sequence of length 3k+1 (remainder 1) saves 1 replacement
  • Deleting 3 chars from a sequence of length 3k+2 (remainder 2) saves 1 replacement

Incorrect Approach:

# Simply deleting characters without considering optimization
chars_to_remove = password_length - 20
return chars_to_remove + max(replacements_needed, 3 - existing_types)

Correct Approach:

# First handle remainder 0 sequences (most efficient)
if consecutive_count % 3 == 0:
    chars_to_remove -= 1
    replacements_needed -= 1

# Then handle remainder 1 sequences with 2-char removals
two_char_removals = min(replacements_needed, sequences_with_remainder_1, chars_to_remove // 2)

# Finally handle remainder 2 sequences with 3-char removals
three_char_removals = min(replacements_needed, chars_to_remove // 3)

4. Not Handling Edge Cases in the Counting Logic

Failing to properly reset the consecutive count or handle single characters can lead to incorrect calculations.

Incorrect Implementation:

for current_char in password:
    if current_char == previous_char:
        consecutive_count += 1
    else:
        replacements_needed += consecutive_count // 3
        # Forgot to reset consecutive_count!
        previous_char = current_char

Correct Implementation:

for current_char in password:
    if current_char == previous_char:
        consecutive_count += 1
    else:
        replacements_needed += consecutive_count // 3
        consecutive_count = 1  # Reset count for new sequence
        previous_char = current_char
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

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 assets algo monster 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 is a data structure

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

Coding Interview 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

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

Load More