# Java AC Solution

• ``````public class Solution {
TreeMap<Integer, Integer> repeat = new TreeMap<Integer, Integer>();
int missing = 0;
int ops = 0;
int deleteNeeded = 0;

int count = 0;
boolean lower = false, upper = false, digit = false;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= 'a' && c <= 'z') lower = true;
if (c >= 'A' && c <= 'Z') upper = true;
if (c >= '0' && c <= '9') digit = true;
if (i > 0 && c == s.charAt(i - 1)) count++;
else {
if (count >= 3) increaseOne(count);
count = 1;
}
}
if (count >= 3) increaseOne(count);
//count missing letters
if (!lower) missing++;
if (!upper) missing++;
if (!digit) missing++;

if (s.length() < 6) {
for (int i = 0; i < (6 - s.length()); i++)
insertOne();
solveRestByReplace();
} else if (s.length() > 20) {
//solve missing letters by replacing before deleteing
int miss = missing;
for (int i = 0; i < miss; i++)
replaceOne();
//while it can not be solved by deleting only, replace one letter first
deleteNeeded = countDelete();
while (s.length() - 20 < deleteNeeded)
replaceOne();
for (int i = 0; i < (s.length() - 20); i++)
deleteOne();
} else {
solveRestByReplace();
}
return ops;
}

private void solveRestByReplace() {
int miss = missing;
for (int i = 0; i < miss; i++)
replaceOne();
for (int key : repeat.keySet()) {
int count = repeat.get(key) * (key / 3);
if (missing > 0) missing -= count;
ops += count;
}
}

private void insertOne() {
ops++;
if (missing > 0) missing--;
if (repeat.size() == 0) return;
Integer key = repeat.firstKey();
decreaseOne(key);
if (key > 4) increaseOne(key - 2);
}

private void deleteOne() {
ops++;
if (repeat.size() == 0) return;
Integer key = repeat.firstKey();
decreaseOne(key);
if (key > 3) increaseOne(key - 1);
}

private void replaceOne() {
ops++;
if (missing > 0) missing--;
if (repeat.size() == 0) return;
Integer key = repeat.lastKey();
decreaseOne(key);
if (key == 3) {
deleteNeeded -= 1;
} else if (key == 4) {
deleteNeeded -= 2;
increaseOne(1);
} else {
deleteNeeded -= 3;
increaseOne(key - 3);
}
}

private int countDelete() {
int res = 0;
for (int key : repeat.keySet()) {
res += (key - 2) * repeat.get(key);
}
return res;
}

private void increaseOne(int key) {
if (!repeat.containsKey(key)) repeat.put(key, 0);
repeat.put(key, repeat.get(key) + 1);
}

private void decreaseOne(int key) {
if (repeat.containsKey(key)) {
repeat.put(key, repeat.get(key) - 1);
if (repeat.get(key) == 0) repeat.remove(key);
}
}
}
``````

• The idea is that in insert(), delete() and replace() function, solve as many problem as possible at the same time instead of just insert, delete or replace.

• Your code is wrong, for example in the case "aaaabaaaaaa123456789F"