```
class Solution {
public:
int strongPasswordChecker(string s) {
int n = s.size();
// check whether each category of lowercase, uppercase, digit exists
vector<int> missing(3,0);
for (int i = 0; i < n; ++i) {
if (s[i] >= 'a' && s[i] <= 'z')
missing[0] = 1;
else if (s[i] >= 'A' && s[i] <= 'Z')
missing[1] = 1;
else if (s[i] >= '0' && s[i] <= '9')
missing[2] = 1;
}
// toInsert is how many categores to insert or replace, ranging 0-3
int toInsert = 0;
for (int i = 0; i < 3; ++i)
if (missing[i] == 0)
++toInsert;
int res = 0; // res is output result
// n < 6 is easy; either 'toInsert' or (6-n) times insertion will fix it
if (n < 6)
res = max(toInsert, 6-n);
// n >= 6 and n <= 20; 1 replacement will fix 3 continuous letters;
// count the sequence of 3 repeating letters; result is max of sequence amounts and 'toInsert'
else if (n <= 20) {
int count = 1;
for (int i = 1; i < n; ++i) {
if (s[i] == s[i-1])
++count;
else
count = 1;
if (count >= 3) {
++res;
count -= 3;
}
}
res = max(res, toInsert);
}
// n > 20; 'toInsert' is how many to replace; 'toDelete' is extra letters;
else {
// conts are the length of all repeating sequence >= 3
vector<int> conts;
int start = 0, length = 0, k = 1;
while (k < n) {
while (k < n && s[k] == s[start])
++k;
length = k-start;
start = k;
if (length >= 3) conts.push_back(length);
}
// use 'toInsert' to do replacements first; Because n > 20, replacement is better than insertion
// 1 replacement will fix 3 continuous letters;
// using greedy procedures, replace sequence longer than or equal to 5 first,
// then on sequences >= 4, last >= 3;
// as long as sequence >= 5, the order doesn't matter;
res = toInsert;
// tmp is the critical length, decreasing from 5 to 3;
// The following loop will be done in 3 passes, and it generally terminates early
// due to 'toInsert' <= 3
// If there is no repeating sequence >= 3, 'toInsert' times replacement is still required
int tmp = 5;
while (toInsert > 0 && tmp >= 3) {
int i = 0;
while (toInsert > 0 && i < conts.size()) {
while (toInsert > 0 && conts[i] >= tmp) {
--toInsert;
conts[i] -= 3;
}
++i;
}
--tmp;
}
// toDelete is the extra letters to delete
int toDelete = n-20;
res += toDelete;
/* using greedy procedures: first, delete 1 letter from sequences with length%3 = 0,
i.e. 3, 6, 9 ...; second, delete 2 letters from length%3 = 1;
finally, all length%3 = 2 (first and second step ensures this);
still 3 passes; tmp increase from 0 to 2;
after deletion, repeating sequence >= 3 may still exist;
or, no repeating sequence left before finishing deletion;*/
tmp = 0;
while (toDelete > 0 && tmp < 3) {
// step is delete letters in every step; it is min of toDelete and tmp+1
int i = 0, step = 0;
while (toDelete > 0 && i < conts.size()) {
while (conts[i] >= 3 && toDelete > 0 && conts[i]%3 == tmp) {
step = min(toDelete, tmp+1);
toDelete -= step;
conts[i] -= step;
}
++i;
}
++tmp;
}
// the following step is similar to the case n <= 20;
//if there is repeating sequence >= 3 left, count how many replacements required;
for (int i = 0; i < conts.size(); ++i)
res += conts[i]/3;
}
return res;
}
};
```