# Very Easy and Simple O(n) solution (20 lines Python, Java)

• Analysis/Usage of 3 operations:
Insert: Able to fix repeat and add missing element (e.g. uppercase/lowercase/digit) => only use in case A.
Delete: Able to fix repeat (by certain number) => only use it in case B.
Replace: Able to fix repeat and add missing element => use in A/B/C

Steps:

1. Check the of type of characters(uppercase/lowercase/digit/others) and get length of repeats. O(n)
2. Fix repeat in Three different cases:
• case A. (L < 6): Not only Repeat but also Missing element can be fixed by insert at same time. O(1)
• case B. (L > 20): Fix by delete (and replace if needed). O(occurance of repeat)
• case C. (6 <= L <= 20): Should be fixed by replace only. O(occurance of repeat)
1. Final check (Fix missing element): If still any missing => fix it by replace. ~O(1)

Detailed explanation can be referred to comments.

Python:

``````class Solution(object):
length, repeat, types, i, j = len(s), [], [False]*4, 0, 1

while i < length:
while i+j < length and s[i+j] == s[i]: j += 1
if j >= 3: repeat += j,                     # get repeats
types[self.classifier(s[i])] = True         # check lower/upper/digit
i, j = i+j, 1

insert, delete, replace = 0, 0, 0

if length < 6: insert = 6-length                # Case A.

elif length > 20:   # Case B. Fix repeat by (replace+delete), should > all solve by replace
delete, allbydel = length-20, sum([r-2 for r in repeat])
if delete < allbydel:     # repeat solved by both delete and replace
replace = max(sum([r//3 for r in repeat])-delete, ((allbydel-delete)+2)//3)

else:               # Case C. fix repeat only by replace
for rp in repeat: replace += rp//3

# final check: if replace less than missing
return insert+delete+max(replace, types[:-1].count(False)-insert)

def classifier(self, c):
# types: 0 = lowercase, 1 = uppercase, 2 = digit, 3 = others (None of above)
if c.islower(): return 0
elif c.isupper(): return 1
elif c.isdigit(): return 2
else: return 3
``````

Java Version: (I think it should be able to do some improvement)

``````public class Solution {
int length = s.length();
ArrayList<Integer> rptlen = new ArrayList<Integer>();
Boolean[] types = {false, false, false, false};
int i = 0;
int j = 1;

while (i < length) {
while ((i+j < length) && (s.charAt(i) == s.charAt(i+j))) {j += 1;}
if (j >= 3) {
}
int tmp = classifier(s.charAt(i));
types[tmp] = true;
i += j;
j = 1;
}
Integer[] work = {0,0,0};       // insert, delete, replace
if (length < 6) {
work[0] = 6-length;
}
else if (length > 20) {
work[1] = length-20;
int allbydel = 0;
int tmp = 0;
for (int k = 0; k < rptlen.size(); k++) {
allbydel += (rptlen.get(k)-2);
tmp += rptlen.get(k)/3;
}
if (work[1] < allbydel) {
work[2] = Math.max(tmp-work[1], (allbydel-work[1]+2)/3);
}
}
else {
for (int x = 0; x < rptlen.size(); x++) {
work[2] += rptlen.get(x)/3;
}
}

int countmiss = 0;
for (int t = 0; t < 3; t ++) { if (types[t] == false) countmiss++;}
return work[0]+work[1]+Math.max(work[2], countmiss-work[0]);
}
private int classifier(char c) {
if (Character.isUpperCase(c)) return 0;
else if (Character.isLowerCase(c)) return 1;
else if (Character.isDigit(c)) return 2;
else return 3;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.