Another Java solution 2ms - Two pass to make repeating character handling more clear


  • 0
    S

    Got this solution by repeatedly hitting submit. Figuring out the test cases is really important for this one.

    This solution scans the password string twice.
    First pass: check lacks of lower/upper/digit char.
    Second pass: deals with repeating characters case based on the current length of the character.

    public int strongPasswordChecker(String s) {
            if(s==null || s.length()==0) {
                return 6;
            }
            boolean lower = false, upper = false, digit = false;
            int distance = 0, len = s.length();
            
            ArrayList<Integer> repeating  = new ArrayList<>();
            char prev = '\0';
            int count = 0;
            for(char c:s.toCharArray()) {
                lower |= c>='a' && c<='z';
                upper |= c>='A' && c<='Z';
                digit |= c>='0' && c<='9';
                if(c==prev) {
                    count++;
                } else {
                    if(count>=3) {
                        repeating.add(count);
                    }
                    count = 1;
                    prev =c;
                }
            }
            if(count>=3) {
                repeating.add(count);
            }
            int required = (lower?0:1)+(upper?0:1)+(digit?0:1);
            int patch = 0;
            Collections.sort(repeating);
            int i = 0;
            while(i<repeating.size()) {
                int c = repeating.get(i);
                if(len>20) {
                    int delta = Math.min(len-20,c-2);
                    c -= delta;
                    len -= delta;
                    distance += delta;
                }
                if(len<=20 && len>=6) {
                    distance += c/3;
                    patch += c/3;
                } else if(len<6) {
                    patch += 1 + len-6;
                    distance += patch;
                    len = 6;
                }
                i++;
            }
            if(len<6) {
                distance += 6-len;
                patch += 6-len;
            } else if(len>20) {
                distance += len-20;
            }
            required -= patch;
            return distance+Math.max(required,0);
        }
    

  • 0
    Y

    @stloki-gmail-com Your solution is much easier to be understood. However, you can add some comments to explain why it works to remove, replace, or insert a character for three different cases. Also, `len' is the length of ``current'' password.


  • 0
    S

    @yuhaowang001 Thx! Added some explanation but I guess you already got the gist by reading the code.


  • 0
    W

    It fails the case: "aaaabbaaabbaaa123456A"

    It should return 3, but not 4


  • 0
    Y

    @wencan-luo
    Yes, you are right. It should be 3, not 4. One possible series of updates could be:

    1. replace the third "a" to "b" or whatever
    2. remove one "a" from the second cluster of 'a'
    3. remove one "a" from the third cluster of 'a'

    The test case should be added to the system.
    And the solution should be updated.


  • 0
    S

    @yuhaowang001 Yeah, need to rethink about it.


  • 0

    @wencan.luo Thanks, I have added your test case.


  • 0
    S

    Failed with case "aaaaaaaAAAAAA6666bbbbaaaaaaABBC"

    @stloki-gmail-com said in Another Java solution 2ms - Two pass to make repeating character handling more clear:

    public int strongPasswordChecker(String s) {
    if(s==null || s.length()==0) {
    return 6;
    }
    boolean lower = false, upper = false, digit = false;
    int distance = 0, len = s.length();

        ArrayList<Integer> repeating  = new ArrayList<>();
        char prev = '\0';
        int count = 0;
        for(char c:s.toCharArray()) {
            lower |= c>='a' && c<='z';
            upper |= c>='A' && c<='Z';
            digit |= c>='0' && c<='9';
            if(c==prev) {
                count++;
            } else {
                if(count>=3) {
                    repeating.add(count);
                }
                count = 1;
                prev =c;
            }
        }
        if(count>=3) {
            repeating.add(count);
        }
        int required = (lower?0:1)+(upper?0:1)+(digit?0:1);
        int patch = 0;
        Collections.sort(repeating);
        int i = 0;
        while(i<repeating.size()) {
            int c = repeating.get(i);
            if(len>20) {
                int delta = Math.min(len-20,c-2);
                c -= delta;
                len -= delta;
                distance += delta;
            }
            if(len<=20 && len>=6) {
                distance += c/3;
                patch += c/3;
            } else if(len<6) {
                patch += 1 + len-6;
                distance += patch;
                len = 6;
            }
            i++;
        }
        if(len<6) {
            distance += 6-len;
            patch += 6-len;
        } else if(len>20) {
            distance += len-20;
        }
        required -= patch;
        return distance+Math.max(required,0);
    }

Log in to reply
 

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