# Java O(n) Greedy solution with super clear explanation

• We discuss in three cases:

1. Case (n=s.length)<6: return 6-n>nMiss?6-n:nMiss, where nMiss = hasLower?0:1+hasUpper?0:1+hasDigit?0:1; (just check every possible n, using appropriate insertions)

2. Case n>=6&&n<=20: Replacement is the best choice! (Replacing every third by another char is the best change.) return max(nMiss, nRep=sum{ni/3}), where ni is the length of a substring with repeating characters (SSRC).

3. Case n>20: It is for sure that (n-20) deletions must be applied no matter what, and for sure that no insertions are needed (since 1 insert needs 1 delete, which is equivalent to 1 replace+1 delete or even 1 delete). Hence we greedily apply deletions first.

Greedy strategies for applying deletions - clearly the best choice is to apply on a SSRC to possibly reduce nRep (when the length of s becomes 20). Immediately, we have the best of the best choice is to delete a char of a SSRC of length 3k (recalling how nRep is calculated as in case 2), and that length becomes 3(k-1)+2. Hence if possible, we apply 1 del per each such SSRC.

If still delete-able, the second best is to apply del on a SSRC of length 3k+1, (since nRep is reduced by 1 per 2 del, but if applying on 3k+2, nRep is reduced by 1 per 3 del). Notice that applying 1 del on such a SSRC makes its length 3k, and immediately this has the highest priority for the next possible deletion. Hence if possible, we apply 2 del per each such SSRC (to make its length become 3(k-1)+2).

If still delete-able, we then apply del on each (updated) SSRC until its length =2. Notice that nRep is reduced by 1 per 3 del since each has length 3k+2.

If still delete-able, return n-20+nMiss, (n-20 del, nMiss many rep).

Otherwise, return n-20+max(updated_nRep, nMiss).

``````public int strongPasswordChecker(String s) {
int n = s.length();
boolean hasLower = false, hasUpper = false, hasDigit = false;
int nRep = 0, sum = 0; // sum=sum{length>=3 of a SSRC}
int[] m = new int[3]; // # of SSRC of length 3k, 3k+1, 3k+2

int i = 0, j, t;
char c;
while (i < n) {
c = s.charAt(i);

hasLower |= (c >= 'a' && c <= 'z');
hasUpper |= (c >= 'A' && c <= 'Z');
hasDigit |= (c >= '0' && c <= '9');

j = i + 1;
while (j < n && s.charAt(j) == c)
j++;

t = j - i;
if (t >= 3) {
nRep += t / 3;
sum += t;
m[t % 3]++;
}
i = j;
}

int nMiss = (hasLower ? 0 : 1) + (hasUpper ? 0 : 1) + (hasDigit ? 0 : 1);

if (n < 6)
return (6 - n) > nMiss ? (6 - n) : nMiss;

if (n <= 20)
return Math.max(nRep, nMiss);

// n > 20
int nDel = n - 20;
if (nDel <= m[0])
return nDel + Math.max(nRep - nDel, nMiss);

int rNDel = nDel - m[0];
nRep -= m[0];
if (rNDel <= 2 * m[1])
return nDel + Math.max(nRep - rNDel / 2, nMiss);

rNDel -= 2 * m[1];
nRep -= m[1];
if (nDel <= sum - 2 * (m[0] + m[1] + m[2]))
/**
* This condition is equivalent to nDel-m[0]-2m[1]<=
* sum{3(k_i-1)}+sum{3(k'_i-1)}+sum{3k''_i},
* where {3k_i, 1<=i<=m[0]}, {3k'_i+1, 1<=i<=m[1]},
* {3k''_i+2, 1<=i<=m[2]} are the sets of lengths of SSRCs
*/
return nDel + Math.max(nRep - rNDel / 3, nMiss);

return nDel + nMiss;
}
``````

• The best algorithm and explanation so far. Thanks.

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