Your solution is easy to understand and works well with the cases s.length() < 6 and 6<= s.length() <= 20.

However when s.length() > 20, the way to delete is not optimal.

For example, test case "aaaaaaaAAAAAA6666bbbbaaaaaaABBC", this solution returns 14, but the correct answer is 13.

After sorting, the posted solution finds n such that sum(groups(0...n-1) < 20 and groups(0...n) >= 20), and delete whatever beyond n. The input string length is 31, so 11 letters needs to be deleted. And with the posted solution, we first delete the group "aaaaaaa" ( 7 a's), then we can do 4 additional deletion to make the replacement of next steps as less as possible.

The flow is

"aaaaaaaAAAAAA6666bbbbaaaaaaABBC" => delete 7 a's, "AAAAAA6666bbbbaaaaaaABBC" => delete 1A from the 6 A's group=> "AAAAA6666bbbbaaaaaaABBC" => delete 1 a from the 6 a's group => "AAAAA6666bbbbaaaaaABBC" => delete 2 6's from the 4 6's group => "AAAAA66bbbbaaaaaABBC" => done with 11 deletions, break;

Next we need 3 replacements: 1 to change AAAAA to e.g. AAxAA

1 to change bbbb to e.g. bbxb

and one to change aaaaa to e.g. aaxaa

the final string is "AAxAA66bbxbaaxaaABBC", there are 11 + 3 = 14 operations.

++++++++++++++++++++++++++++++++++++

However, a better deletion way is: instead of deleting the 7 a's, try to reduce more replacements as possible.

e.g.

From "aaaaaaaAAAAAA6666bbbbaaaaaaABBC" => delete 5 a's from the first 7 a's group => "aaAAAAAA6666bbbbaaaaaaABBC" => delete 1 A from the next 6 A's group => "aaAAAAA6666bbbbaaaaaaABBC" => delete 2 6's from the next 4 6's group => "aaAAAAA66bbbbaaaaaaABBC" => delete 2 b's from the next 4 b's group => "aaAAAAA66bbaaaaaaABBC" => delete 1 a from the next 6 a's group => "aaAAAAA66bbaaaaaABBC" => now the string length is 20, and we have done 11 deletions.

Then we need to break repeats: change AAAAA to AAxAA, aaaaa to aaxaa, only 2 replacements required.

The final string is "aaAAxAA66bbaaxaaABBC", this is valid, and the total ops is 11 deletions + 2 replacements = 13 ops, which is better than 14 operations.

@sangyezi said in java with detailed explanation:

public int strongPasswordChecker(String s) {

int minReplace = getMinReplace(s);

if (s.length() < 6){
int insersion = 6 - s.length();
return Math.max(insersion, minReplace);
} else if (s.length() <= 20){
List<Integer> groups = generateGroups(s);
int replace = 0;
for (int group : groups){
replace += group / 3;
}
return Math.max(replace, minReplace);
} else {
List<Integer> groups = generateGroups(s);
Collections.sort(groups);
int charCount = 0;
int n = 0;
while (charCount < 20 && n < groups.size()) {
charCount += groups.get(n);
n++;
}
while (groups.size() > n) {
groups.remove(groups.size() - 1);
}
charCount = 0;
int badGroup = 0;
for (int i = 0; i < groups.size(); i++) {
if (groups.get(i) > 20) {
groups.set(i, 20);
}
charCount += groups.get(i);
if (groups.get(i) > 2){
badGroup++;
}
}
int deletion = s.length() - 20;
int toDelete = charCount - 20;
int remainder = 0;
while (toDelete > 0 && badGroup > 0) {
for (int i = 0; i < n; i++) {
if (groups.get(i) > 2 && groups.get(i) % 3 == remainder) {
int del = Math.min(toDelete, remainder + 1);
groups.set(i, groups.get(i) - del);
toDelete -= del;
if (groups.get(i) <= 2){
badGroup--;
}
if (toDelete == 0 || badGroup == 0) {
break;
}
}
}
remainder = (remainder + 1) % 3;
}
int replace = 0;
for (int i = 0; i < groups.size(); i++) {
replace += groups.get(i) / 3;
}
return deletion + Math.max(replace, minReplace);
}
}
/**
* generate sorted groups
* groups: # of continuous characters in S
*/
private List<Integer> generateGroups(String s){
List<Integer> groups = new ArrayList<>();
for (int i = 0 ; i < s.length();){
int j = i;
while (j < s.length() && s.charAt(j) == s.charAt(i)){
j++;
}
groups.add(j - i);
i = j;
}
return groups;
}
/**
* return # of replacements needed to satisfy 2
*/
private int getMinReplace(String s){
boolean[] dls = new boolean[3];
for(char c : s.toCharArray()){
dls[getClass(c)] = true;
}
int replace = 0;
for (int i = 0; i < dls.length; i++){
if (!dls[i]) replace++;
}
return replace;
}
private int getClass(char c){
if (c >= '0' && c <= '9'){
return 0;
} else if (c >= 'a' && c <= 'z'){
return 1;
} else{
return 2;
}
}