Leetcode 420. Strong Password Checker

Problem Explanation and Solution Walkthrough

This problem requires us to devise a strong password following certain conditions. In the problem, a strong password should have:

• at least 6 characters and at most 20 characters
• at least one lowercase letter, one uppercase letter, and one digit
• does not contain any three repeating characters in a row.

Our function needs to determine the minimum number of changes required to transform a given string into a strong password. Changes can be made by either inserting, deleting, or replacing any character. If the string already forms a strong password, the function should return 0.

Let's understand this with an example:

Consider s = "aBc12#".

This string meets all the criteria for a strong password already, and therefore, no changes are necessary. Therefore, the function will return 0.

Now let us consider the approach for the solution using the string s = "AAA111":

In this case, we have 6 characters, so length is fine, we have at least one uppercase character and one digit, however there are two problems. We have no lowercase character and we have three repeating characters in a row. In our function, we first calculate all missing characters (uppercase, lowercase or digit) as missing, and calculate a total replace count (1 replace for each 3 repeated characters). If our string length is less than 6, then the missing characters can be inserted while increasing the length to 6, so we return the maximum of 6 - n and missing. If the string length is more than 20, we need to delete characters, and we attempt to replace repeating characters through deletions wherever possible. The result is computed as the total deletions required plus the max of remaining replace and missing.

Python Solution

1
2python
3class Solution:
4    def strongPasswordChecker(self, s: str) -> int:
5        missing = 3
6        if any(c.isupper() for c in s):
7            missing -= 1
8        if any(c.islower() for c in s):
9            missing -= 1
10        if any(c.isdigit() for c in s):
11            missing -= 1
12
13        replace = 0
14        one = two = 0
15        p = 2
16        while p < len(s):
17            if s[p] == s[p-1] == s[p-2]:
18                length = 2
19                while p < len(s) and s[p] == s[p-1]:
20                    length += 1
21                    p += 1
22                
23                replace += length // 3
24                if length % 3 == 0:
25                    one += 1
26                elif length % 3 == 1:
27                    two += 1
28            else:
29                p += 1
30
31        if len(s) < 6:
32            return max(missing, 6 - len(s))
33        elif len(s) <= 20:
34            return max(missing, replace)
35        else:
36            deletes = len(s) - 20
37            replace -= min(deletes, one)
38            replace -= min(max(deletes - one, 0), two * 2) // 2
39            replace -= max(deletes - one - two * 2, 0) // 3
40
41            return deletes + max(missing, replace)

In the Python solution, we start by initializing a missing counter, which counts the missing characters types (uppercase, lowercase, digit). The for loops with the any() function check if there exists at least one of each type in s, and if so, decrements the missing count. We similarly calculate counts for replacement of three repeating characters and the one and two-count clusters that can be handled with deletions efficiently. If length is not within [6, 20] we handle it by returning appropriate amounts. The final return computes the total deletions required plus the max of remaining replace and missing. We use string functions like isdigit(), islower() and isupper() to check for digit, lower case and upper case characters. If any string has a lowercase, uppercase, or a digit, it is removed from the missing count.## JavaScript Solution

In JavaScript, the implementation would be relatively similar. We're using the match() method with regular expressions to check for uppercase, lowercase, and digit characters.

1
2javascript
3var strongPasswordChecker = function(s) {
4    let missing = 3
5    if (s.match(/[A-Z]/g)) missing--;
6    if (s.match(/[a-z]/g)) missing--;
7    if (s.match(/[0-9]/g)) missing--;
8
9    let replace = 0;
10    let one = 0;
11    let two = 0;
12    let p = 2;
13    while (p < s.length) {
14        if (s[p] == s[p-1] && s[p] == s[p-2]) {
15            let len = 2;
16            while (p < s.length && s[p] == s[p-1]) {
17                len++;
18                p++;
19            }
20            replace += Math.floor(len / 3);
21            if (len % 3 === 0) one++;
22            else if (len % 3 === 1) two++;
23        } else {
24            p++;
25        }
26    }
27
28    if (s.length < 6) {
29        return Math.max(6 - s.length, missing);
30    } else if (s.length <= 20) {
31        return Math.max(missing, replace);
32    } else {
33        let deletes = s.length - 20;
34        replace -= Math.min(deletes, one * 1);
35        replace -= Math.floor(Math.min(Math.max(deletes - one, 0), two * 2) / 2);
36        replace -= Math.floor(Math.max(deletes - one - 2 * two, 0) / 3);
37        return deletes + Math.max(missing, replace);
38    }
39};

Java Solution

In Java, we would follow similar logic but use standard Java methods to identify uppercase, lowercase, and digit characters.

1
2java
3class Solution {
4    public int strongPasswordChecker(String s) {
5        int res = 0, a = 1, up = 1, lo = 1;
6        int[] repeat = new int[s.length()];
7        for (int i = 0; i < s.length();) {
8            char c = s.charAt(i);
9            int j = i;
10            while (i < s.length() && s.charAt(i) == c) {
11                i++;
12            }
13            int different = i - j;
14            repeat[j] = different;
15            if (different >= 3) 
16            {
17                res += different / 3;
18            }
19            if (c >= 'a' && c <= 'z')
20                lo = 0;
21            else if (c >= 'A' && c <= 'Z')
22                up = 0;
23            else if (c >= '0' && c <= '9')
24                a = 0;
25        }
26
27        int missing = a + lo + up;
28        if (s.length() < 6) {
29            res += missing + Math.max(0, 6 - (s.length() + missing));
30        } else if (s.length() > 20) {
31            int overLen = Math.max(s.length() - 20, 0), leftOver = 0;
32            res += overLen;
33
34            for (int k = 1; k < 3; k++) {
35                for (int i = 0; i < s.length() && overLen > 0; i++) {
36                    if (repeat[i] < 3 || repeat[i] % 3 != (k - 1)) continue;
37                    repeat[i] -= Math.min(overLen, k);
38                    overLen -= k;
39                }
40            }
41
42            for (int i = 0; i < s.length(); i++) {
43                if (repeat[i] >= 3 && overLen > 0) {
44                    int need = repeat[i] - 2;
45                    repeat[i] -= overLen;
46                    overLen -= need;
47                }
48
49                if (repeat[i] >= 3) 
50                    leftOver += repeat[i] / 3;
51            }
52
53            res += Math.max(missing, leftOver);
54        } else 
55            res += missing;
56        
57        return res;
58    }
59}

The Java solution is a bit more complex due to the specifics of the Java language. The solution iterates over the character string, computes the count of missing types, calculates replace count for three repeated characters and handles the cases when length is not within [6, 20]. The charAt() method is used to get the character at the specific index, and Unicode value ranges to check for uppercase, lowercase and digit characters.