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


  • 0

    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):
        def strongPasswordChecker(self, s):
            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 {
        public int strongPasswordChecker(String s) {
            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) {
                    rptlen.add(j);
                }
                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;
        }
    }
    

Log in to reply
 

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