Problem#
A password is considered strong if the below conditions are all met:
It has at least 6 characters and at most 20 characters.
It contains at least one lowercase letter, at least one uppercase letter, and at least one digit .
It does not contain three repeating characters in a row (i.e., "B**aaa**bb0" is weak, but "B**aa**b**a**0" is strong).
Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.
In one step, you can:
Insert one character to password,
Delete one character from password, or
Replace one character of password with another character.
Examples#
Example 1:
1
2
Input: password = "a"
Output: 5
Example 2:
1
2
Input: password = "aA1"
Output: 3
Example 3:
1
2
Input: password = "1337C0d3"
Output: 0
Solution#
Method 1 - Greedy / Simulation#
Check character types: Count if the password contains at least one lowercase letter, one uppercase letter, and one digit.Handle short passwords (n < 6): If the password is too short, the answer is the maximum of (6 - n) and the number of missing character types.Handle valid length passwords (6 ≤ n ≤ 20): Count the number of replacements needed to fix sequences of three or more repeating characters. The answer is the maximum of the number of replacements and the number of missing character types.Handle long passwords (n > 20): Calculate the number of deletions needed to reduce the length to 20. Use deletions to reduce the number of replacements needed for repeating characters. The answer is the number of deletions plus the maximum of the remaining replacements and the number of missing character types.
Code#
<!-- Tabs:start -->
Cpp
Java
Python
<!-- Tabs:end -->
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
public :
int strongPasswordChecker(string password) {
int types = countTypes(password);
int n = password.size();
if (n < 6 ) return max(6 - n, 3 - types);
if (n <= 20 ) {
int replace = 0 , cnt = 0 ;
char prev = '~' ;
for (char & curr : password) {
if (curr == prev)
++ cnt;
else {
replace += cnt / 3 ;
cnt = 1 ;
prev = curr;
}
}
replace += cnt / 3 ;
return max (replace, 3 - types);
}
int replace = 0 , remove = n - 20 ;
int remove2 = 0 ;
int cnt = 0 ;
char prev = '~' ;
for (char & curr : password) {
if (curr == prev)
++ cnt;
else {
if (remove > 0 && cnt >= 3 ) {
if (cnt % 3 == 0 ) {
-- remove;
-- replace;
} else if (cnt % 3 == 1 )
++ remove2;
}
replace += cnt / 3 ;
cnt = 1 ;
prev = curr;
}
}
if (remove > 0 && cnt >= 3 ) {
if (cnt % 3 == 0 ) {
-- remove;
-- replace;
} else if (cnt % 3 == 1 )
++ remove2;
}
replace += cnt / 3 ;
int use2 = min(min(replace, remove2), remove / 2 );
replace -= use2;
remove -= use2 * 2 ;
int use3 = min(replace, remove / 3 );
replace -= use3;
remove -= use3 * 3 ;
return (n - 20 ) + max(replace, 3 - types);
}
int countTypes (string& s) {
int a = 0 , b = 0 , c = 0 ;
for (char & ch : s) {
if (islower(ch))
a = 1 ;
else if (isupper(ch))
b = 1 ;
else if (isdigit(ch))
c = 1 ;
}
return a + b + c;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
public int strongPasswordChecker (String password) {
int types = countTypes(password);
int n = password.length ();
if (n < 6) {
return Math.max (6 - n, 3 - types);
}
char [] chars = password.toCharArray ();
if (n <= 20) {
int replace = 0;
int cnt = 0;
char prev = '~' ;
for (char curr : chars) {
if (curr == prev) {
++ cnt;
} else {
replace += cnt / 3;
cnt = 1;
prev = curr;
}
}
replace += cnt / 3;
return Math.max (replace, 3 - types);
}
int replace = 0, remove = n - 20;
int remove2 = 0;
int cnt = 0;
char prev = '~' ;
for (char curr : chars) {
if (curr == prev) {
++ cnt;
} else {
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
-- remove;
-- replace;
} else if (cnt % 3 == 1) {
++ remove2;
}
}
replace += cnt / 3;
cnt = 1;
prev = curr;
}
}
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
-- remove;
-- replace;
} else if (cnt % 3 == 1) {
++ remove2;
}
}
replace += cnt / 3;
int use2 = Math.min (Math.min (replace, remove2), remove / 2);
replace -= use2;
remove -= use2 * 2;
int use3 = Math.min (replace, remove / 3);
replace -= use3;
remove -= use3 * 3;
return (n - 20) + Math.max (replace, 3 - types);
}
private int countTypes (String s) {
int a = 0, b = 0, c = 0;
for (char ch : s.toCharArray ()) {
if (Character.isLowerCase (ch)) {
a = 1;
} else if (Character.isUpperCase (ch)) {
b = 1;
} else if (Character.isDigit (ch)) {
c = 1;
}
}
return a + b + c;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution :
def strongPasswordChecker (self, password: str) -> int:
def countTypes (s):
a = b = c = 0
for ch in s:
if ch. islower():
a = 1
elif ch. isupper():
b = 1
elif ch. isdigit():
c = 1
return a + b + c
types = countTypes(password)
n = len(password)
if n < 6 :
return max(6 - n, 3 - types)
if n <= 20 :
replace = cnt = 0
prev = '~'
for curr in password:
if curr == prev:
cnt += 1
else :
replace += cnt // 3
cnt = 1
prev = curr
replace += cnt // 3
return max(replace, 3 - types)
replace = cnt = 0
remove, remove2 = n - 20 , 0
prev = '~'
for curr in password:
if curr == prev:
cnt += 1
else :
if remove > 0 and cnt >= 3 :
if cnt % 3 == 0 :
remove -= 1
replace -= 1
elif cnt % 3 == 1 :
remove2 += 1
replace += cnt // 3
cnt = 1
prev = curr
if remove > 0 and cnt >= 3 :
if cnt % 3 == 0 :
remove -= 1
replace -= 1
elif cnt % 3 == 1 :
remove2 += 1
replace += cnt // 3
use2 = min(replace, remove2, remove // 2 )
replace -= use2
remove -= use2 * 2
use3 = min(replace, remove // 3 )
replace -= use3
remove -= use3 * 3
return n - 20 + max(replace, 3 - types)
Complexity#
⏰ Time complexity: O(n). Each pass through the password (to count types, find repeats, and process deletions/replacements) is linear in the length of the password.
🧺 Space complexity: O(1). Only a constant number of variables are used, regardless of input size.