## Description

LeetCode Problem 420.

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 doesnot contain three repeating characters in a row (i.e.,”…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met).

In one step, you can:

• Insert one character to password,
• Delete one character from password, or
• Replaceone character of password with another character.

Example 1:

``````1
2
Output: 5
``````

Example 2:

``````1
2
Output: 3
``````

Example 3:

``````1
2
Output: 0
``````

Constraints:

• 1 <= password.length <= 50
• password consists of letters, digits, dot’.’ or exclamation mark ‘!’.

## Sample C++ Code

``````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
class Solution {
public:
bool isLower(char c) { return c >= 'a' && c <= 'z'; }
bool isUpper(char c) { return c >= 'A' && c <= 'Z'; }
bool isNumber(char c) { return c >= '0' && c <= '9'; }

if (!n) return 6;
int repeat = 1, replace = 0, remove = 0, add = 0;
int lower = isLower(cur), upper = isUpper(cur), number = isNumber(cur);
vector<int> repeatVec;
for (int i = 1; i < n; ++i) {
if (password[i] != cur || i == n-1) {
replace += repeat/3;
remove += max(0, repeat-2);
if (repeat > 2)
repeatVec.push_back(repeat);
repeat = 1;
}
}
int miss = 0;
if (!lower) ++miss;
if (!upper) ++miss;
if (!number) ++miss;
if (n < 6) return max(max(6 - n, miss), add);
if (n <= 20) return max(replace, miss);
int needRemove = n - 20;
if (needRemove >= remove)
return needRemove + miss;
else {
int R = needRemove, m = repeatVec.size();
vector<vector<int>> dp(R+1, vector<int>(m+1, INT_MAX));
dp[0][0] = 0;
for (int j = 1; j <= m; ++j)
dp[0][j] = dp[0][j-1] + repeatVec[j-1]/3;
for (int r = 1; r <= R; ++r)
for (int j = 1; j <= m; ++j)
for (int s = 0; s <= min(repeatVec[j-1]-2, r); ++s)
if (dp[r-s][j-1] < INT_MAX)
dp[r][j] = min(dp[r][j], dp[r-s][j-1] + (repeatVec[j-1]-s)/3);
return needRemove + max(dp[R][m], miss);
}
}
};
``````