Java - O(n) simple solution

• Repeating sequences like aaa with len % 3 == 0, we replace by deleting one character. For any repeating sequences aaaa with len % 3 == 1, we can reduce one replacement by deleting two character. For the rest, reduce every replacement by deleting three character.

This is my first post and pls do let me know if any errors or improvements. Thank you

``````public class Solution {

char [] str = s.toCharArray();
boolean isUpper = false, isLower = false, isDigit = false;
int missinType = 3;
for(char c: str)
{
if(!isUpper && Character.isUpperCase(c)) { isUpper = true; missinType-=1; } //uppercase
if(!isLower && Character.isLowerCase(c)) { isLower = true; missinType-=1; } //lowercase
if(!isDigit && Character.isDigit(c)) { isDigit = true; missinType-=1; } //atleast one number

}

int totalChangeCnt = 0, OneChangeCnt =0, TwoChangeCnt =0, pos=2;
while(pos < s.length())
{
if(str[pos]==str[pos-1] && str[pos-1]==str[pos-2] && str[pos-2]==str[pos])
{
int length = 2;
while(pos < s.length() && str[pos]==str[pos-1])
{
length += 1; pos +=1;
}
totalChangeCnt += length/3;
if(length%3==0) OneChangeCnt += 1;
else if(length%3==1) TwoChangeCnt += 1;

}
else
{
pos=pos+1;
}
}

if(s.length()<6)
return Math.max(missinType, 6-s.length());
else if(s.length() <=20)
return Math.max(missinType,totalChangeCnt );
else
{
int deleteCount = s.length()-20;
totalChangeCnt -= Math.min(deleteCount,OneChangeCnt*1)/1;
totalChangeCnt -= Math.min(Math.max(deleteCount - OneChangeCnt, 0), TwoChangeCnt * 2) / 2;
totalChangeCnt -= Math.max(deleteCount - OneChangeCnt - 2 * TwoChangeCnt, 0) / 3;

return deleteCount + Math.max(missinType, totalChangeCnt);
}
}
}

``````

• Hi, there:) I am curious about why you don't calculate `ThreeChangeCnt` in the loop, and then in the ">20" case, you do: `totalChangeCnt -= Math.min(Math.max(deleteCount - OneChangeCnt - 2 * TwoChangeCnt, 0), ThreeChangeCnt * 3) / 3`? Could you explain for me please?

• @dachuan.huang
Since you can always reduce one replacement by deleting three characters, not just length%3==2.
For example, aaa aaa aaa, you can reduce 3 replacement by deleting 3 * 3 = 9 characters.

I really like the solution and add some extra code/variables and inline explanation to make it more readable.

``````public class Solution {
if(s == null || s.length() == 0 ) return 6;
/*Count the changes require for missing types*/
boolean hasDigit=false, hasUpper=false, hasLower=false;
int missType=3;
for (int i = 0; i < s.length(); i++) {
char ch=s.charAt(i);
if (!hasDigit && Character.isDigit(ch)) {
hasDigit=true;
missType--;
}else if (!hasUpper && Character.isUpperCase(ch)) {
hasUpper=true;
missType--;
}else if (!hasLower && Character.isLowerCase(ch)) {
hasLower=true;
missType--;
}
}
/*Count the changes required for repeating chars in a row*/
int nReplace=0, nOneDelete=0, nTwoDelete=0, nThreeDelete=0;
for (int i = 2; i < s.length(); i++){
if(s.charAt(i) == s.charAt(i-1) && s.charAt(i-1) == s.charAt(i-2)){
int len=3;
while(i+1 < s.length() && s.charAt(i+1) == s.charAt(i)){
len++;
i++;
}
nReplace+= len/3; //replace 1 char in each 3 repeating chars can fix it; e.g., aaa aaa -> aab aab
/*Better ways to fix repeating chars, when s.length() > 20 */
if(len%3 == 0) nOneDelete++; //One replace can be reduce to One Delete; e.g. aab aab ->  aab aa
else if(len%3 == 1) nTwoDelete++; //One replace can be reduced to Two Delete; aab aab a -> aab aa
}
}
if (s.length() < 6) {
return Math.max(6-s.length(), missType); //repeating chars problem will be automatically fixed by insertion;
}else if (s.length() <= 20) {
return Math.max(missType, nReplace); //For repeating chars, replace is always a better choice;
}else {
int requiredDelete= s.length()-20; //minimal chars need to be deleted
int nDelete=0; //chars have been deleted
// aab aab -> aab aa ,can save one replace and reduce required Delete by 1
int nToDelete= Math.min(requiredDelete, nOneDelete);
nReplace-= nToDelete; requiredDelete-= nToDelete; nDelete+= nToDelete;
// aab aab a -> aab aa, can save one replace and reduce required Delete by 2
nToDelete = Math.min(requiredDelete, nTwoDelete*2);
nReplace-= nToDelete/2; requiredDelete-= nToDelete; nDelete+= nToDelete;
//Can always reduce one replacement by deleting three characters, not just length%3==2.
//For example, for both aab aab a and aab aab aa, you can reduce 2 replacement by deleting 3 * 2 = 6 characters.
nToDelete = Math.min(requiredDelete, nReplace*3);
nReplace-= nToDelete/3; requiredDelete-= nToDelete; nDelete+= nToDelete;
return Math.max(missType, nReplace)+requiredDelete+nDelete;
}
}
}
``````

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