Java O(n) Greedy solution with super clear explanation


  • 3
    R

    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;
    }
    

  • 0
    C

    The best algorithm and explanation so far. Thanks.


Log in to reply
 

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