Java AC Solution


  • 0
    D
    public class Solution {
        TreeMap<Integer, Integer> repeat = new TreeMap<Integer, Integer>();
        int missing = 0;
        int ops = 0;
        int deleteNeeded = 0;
    
        public int strongPasswordChecker(String s) {
            int count = 0;
            boolean lower = false, upper = false, digit = false;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c >= 'a' && c <= 'z') lower = true;
                if (c >= 'A' && c <= 'Z') upper = true;
                if (c >= '0' && c <= '9') digit = true;
                if (i > 0 && c == s.charAt(i - 1)) count++;
                else {
                    if (count >= 3) increaseOne(count);
                    count = 1;
                }
            }
            if (count >= 3) increaseOne(count);
            //count missing letters
            if (!lower) missing++;
            if (!upper) missing++;
            if (!digit) missing++;
    
            if (s.length() < 6) {
                for (int i = 0; i < (6 - s.length()); i++)
                    insertOne();
                solveRestByReplace();
            } else if (s.length() > 20) {
                //solve missing letters by replacing before deleteing
                int miss = missing;
                for (int i = 0; i < miss; i++)
                    replaceOne();
                //while it can not be solved by deleting only, replace one letter first
                deleteNeeded = countDelete();
                while (s.length() - 20 < deleteNeeded)
                    replaceOne();
                for (int i = 0; i < (s.length() - 20); i++)
                    deleteOne();
            } else {
                solveRestByReplace();
            }
            return ops;
        }
    
        private void solveRestByReplace() {
            int miss = missing;
            for (int i = 0; i < miss; i++)
                replaceOne();
            for (int key : repeat.keySet()) {
                int count = repeat.get(key) * (key / 3);
                if (missing > 0) missing -= count;
                ops += count;
            }
        }
    
        private void insertOne() {
            ops++;
            if (missing > 0) missing--;
            if (repeat.size() == 0) return;
            Integer key = repeat.firstKey();
            decreaseOne(key);
            if (key > 4) increaseOne(key - 2);
        }
    
        private void deleteOne() {
            ops++;
            if (repeat.size() == 0) return;
            Integer key = repeat.firstKey();
            decreaseOne(key);
            if (key > 3) increaseOne(key - 1);
        }
    
        private void replaceOne() {
            ops++;
            if (missing > 0) missing--;
            if (repeat.size() == 0) return;
            Integer key = repeat.lastKey();
            decreaseOne(key);
            if (key == 3) {
                deleteNeeded -= 1;
            } else if (key == 4) {
                deleteNeeded -= 2;
                increaseOne(1);
            } else {
                deleteNeeded -= 3;
                increaseOne(key - 3);
            }
        }
    
        private int countDelete() {
            int res = 0;
            for (int key : repeat.keySet()) {
                res += (key - 2) * repeat.get(key);
            }
            return res;
        }
    
        private void increaseOne(int key) {
            if (!repeat.containsKey(key)) repeat.put(key, 0);
            repeat.put(key, repeat.get(key) + 1);
        }
    
        private void decreaseOne(int key) {
            if (repeat.containsKey(key)) {
                repeat.put(key, repeat.get(key) - 1);
                if (repeat.get(key) == 0) repeat.remove(key);
            }
        }
    }
    

  • 0
    D

    The idea is that in insert(), delete() and replace() function, solve as many problem as possible at the same time instead of just insert, delete or replace.


  • 0
    R

    Your code is wrong, for example in the case "aaaabaaaaaa123456789F"


  • 0

    @RayLLLL Thanks, I have just added your test case.


  • 0
    D

    @RayLLLL Thanks, just updated my solution and it should work now.


Log in to reply
 

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