java with detailed explanation


  • 3
    S

    0_1477253856645_Screen Shot 2016-10-23 at 4.16.42 PM.png

    public class Solution {
        public int strongPasswordChecker(String s) {
            int minReplace = getMinReplace(s);
    
            if (s.length() < 6){
                int insersion = 6 - s.length();
                return Math.max(insersion, minReplace);
            } else if (s.length() <= 20){
                List<Integer> groups = generateGroups(s);
                int replace = 0;
                for (int group : groups){
                    replace += group / 3;
                }
                return Math.max(replace, minReplace);
            } else {
    
                List<Integer> groups = generateGroups(s);
    
                Collections.sort(groups);
    
                int charCount = 0;
                int n = 0;
                while (charCount < 20 && n < groups.size()) {
                    charCount += groups.get(n);
                    n++;
                }
    
                while (groups.size() > n) {
                    groups.remove(groups.size() - 1);
                }
    
                charCount = 0;
    
                int badGroup = 0;
                for (int i = 0; i < groups.size(); i++) {
                    if (groups.get(i) > 20) {
                        groups.set(i, 20);
                    }
                    charCount += groups.get(i);
                    if (groups.get(i) > 2){
                        badGroup++;
                    }
                }
    
                int deletion = s.length() - 20;
    
                int toDelete = charCount - 20;
    
                int remainder = 0;
                while (toDelete > 0 && badGroup > 0) {
    
                    for (int i = 0; i < n; i++) {
                        if (groups.get(i) > 2 && groups.get(i) % 3 == remainder) {
                            int del = Math.min(toDelete, remainder + 1);
                            groups.set(i, groups.get(i) - del);
                            toDelete -= del;
                            if (groups.get(i) <= 2){
                                badGroup--;
                            }
                            if (toDelete == 0 || badGroup == 0) {
                                break;
                            }
                        }
                    }
                    remainder = (remainder + 1) % 3;
                }
    
                int replace = 0;
                for (int i = 0; i < groups.size(); i++) {
                    replace += groups.get(i) / 3;
                }
    
                return deletion + Math.max(replace, minReplace);
            }
        }
    
        /**
         * generate sorted groups
         * groups: # of continuous characters in S
         */
        private List<Integer> generateGroups(String s){
            List<Integer> groups = new ArrayList<>();
            for (int i = 0 ; i < s.length();){
                int j = i;
                while (j < s.length() && s.charAt(j) == s.charAt(i)){
                    j++;
                }
                groups.add(j - i);
                i = j;
            }
            return groups;
        }
    
        /**
         * return # of replacements needed to satisfy 2
         */
        private int getMinReplace(String s){
            boolean[] dls = new boolean[3];
            for(char c : s.toCharArray()){
                dls[getClass(c)] = true;
            }
            int replace = 0;
            for (int i = 0; i < dls.length; i++){
                if (!dls[i]) replace++;
            }
            return replace;
        }
    
        private int getClass(char c){
            if (c >= '0' && c <= '9'){
                return 0;
            } else if (c >= 'a' && c <= 'z'){
                return 1;
            } else{
                return 2;
            }
        }
    }
    

  • 0

    good,more clear and understandable than the other solutions


  • 0
    S

    Your solution is easy to understand and works well with the cases s.length() < 6 and 6<= s.length() <= 20.

    However when s.length() > 20, the way to delete is not optimal.
    For example, test case "aaaaaaaAAAAAA6666bbbbaaaaaaABBC", this solution returns 14, but the correct answer is 13.

    After sorting, the posted solution finds n such that sum(groups(0...n-1) < 20 and groups(0...n) >= 20), and delete whatever beyond n. The input string length is 31, so 11 letters needs to be deleted. And with the posted solution, we first delete the group "aaaaaaa" ( 7 a's), then we can do 4 additional deletion to make the replacement of next steps as less as possible.

    The flow is
    "aaaaaaaAAAAAA6666bbbbaaaaaaABBC" => delete 7 a's, "AAAAAA6666bbbbaaaaaaABBC" => delete 1A from the 6 A's group=> "AAAAA6666bbbbaaaaaaABBC" => delete 1 a from the 6 a's group => "AAAAA6666bbbbaaaaaABBC" => delete 2 6's from the 4 6's group => "AAAAA66bbbbaaaaaABBC" => done with 11 deletions, break;

    Next we need 3 replacements: 1 to change AAAAA to e.g. AAxAA
    1 to change bbbb to e.g. bbxb
    and one to change aaaaa to e.g. aaxaa
    the final string is "AAxAA66bbxbaaxaaABBC", there are 11 + 3 = 14 operations.

    ++++++++++++++++++++++++++++++++++++

    However, a better deletion way is: instead of deleting the 7 a's, try to reduce more replacements as possible.
    e.g.
    From "aaaaaaaAAAAAA6666bbbbaaaaaaABBC" => delete 5 a's from the first 7 a's group => "aaAAAAAA6666bbbbaaaaaaABBC" => delete 1 A from the next 6 A's group => "aaAAAAA6666bbbbaaaaaaABBC" => delete 2 6's from the next 4 6's group => "aaAAAAA66bbbbaaaaaaABBC" => delete 2 b's from the next 4 b's group => "aaAAAAA66bbaaaaaaABBC" => delete 1 a from the next 6 a's group => "aaAAAAA66bbaaaaaABBC" => now the string length is 20, and we have done 11 deletions.

    Then we need to break repeats: change AAAAA to AAxAA, aaaaa to aaxaa, only 2 replacements required.

    The final string is "aaAAxAA66bbaaxaaABBC", this is valid, and the total ops is 11 deletions + 2 replacements = 13 ops, which is better than 14 operations.

    @sangyezi said in java with detailed explanation:

    public int strongPasswordChecker(String s) {
    int minReplace = getMinReplace(s);

        if (s.length() < 6){
            int insersion = 6 - s.length();
            return Math.max(insersion, minReplace);
        } else if (s.length() <= 20){
            List<Integer> groups = generateGroups(s);
            int replace = 0;
            for (int group : groups){
                replace += group / 3;
            }
            return Math.max(replace, minReplace);
        } else {
    
            List<Integer> groups = generateGroups(s);
    
            Collections.sort(groups);
    
            int charCount = 0;
            int n = 0;
            while (charCount < 20 && n < groups.size()) {
                charCount += groups.get(n);
                n++;
            }
    
            while (groups.size() > n) {
                groups.remove(groups.size() - 1);
            }
    
            charCount = 0;
    
            int badGroup = 0;
            for (int i = 0; i < groups.size(); i++) {
                if (groups.get(i) > 20) {
                    groups.set(i, 20);
                }
                charCount += groups.get(i);
                if (groups.get(i) > 2){
                    badGroup++;
                }
            }
    
            int deletion = s.length() - 20;
    
            int toDelete = charCount - 20;
    
            int remainder = 0;
            while (toDelete > 0 && badGroup > 0) {
    
                for (int i = 0; i < n; i++) {
                    if (groups.get(i) > 2 && groups.get(i) % 3 == remainder) {
                        int del = Math.min(toDelete, remainder + 1);
                        groups.set(i, groups.get(i) - del);
                        toDelete -= del;
                        if (groups.get(i) <= 2){
                            badGroup--;
                        }
                        if (toDelete == 0 || badGroup == 0) {
                            break;
                        }
                    }
                }
                remainder = (remainder + 1) % 3;
            }
    
            int replace = 0;
            for (int i = 0; i < groups.size(); i++) {
                replace += groups.get(i) / 3;
            }
    
            return deletion + Math.max(replace, minReplace);
        }
    }
    
    /**
     * generate sorted groups
     * groups: # of continuous characters in S
     */
    private List<Integer> generateGroups(String s){
        List<Integer> groups = new ArrayList<>();
        for (int i = 0 ; i < s.length();){
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)){
                j++;
            }
            groups.add(j - i);
            i = j;
        }
        return groups;
    }
    
    /**
     * return # of replacements needed to satisfy 2
     */
    private int getMinReplace(String s){
        boolean[] dls = new boolean[3];
        for(char c : s.toCharArray()){
            dls[getClass(c)] = true;
        }
        int replace = 0;
        for (int i = 0; i < dls.length; i++){
            if (!dls[i]) replace++;
        }
        return replace;
    }
    
    private int getClass(char c){
        if (c >= '0' && c <= '9'){
            return 0;
        } else if (c >= 'a' && c <= 'z'){
            return 1;
        } else{
            return 2;
        }
    }

Log in to reply
 

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