class Solution {
    // Dec 16th
    private static int[] freqs = new int[26];

    public int leastInterval(char[] tasks, int n) {
        for (char c : tasks) {
            freqs[c-'A']++;
        }
        List<Character> uniqTasks = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            if (freqs[i] != 0 ) uniqTasks.add((char)(i+'A'));
        }

        Deque<Character> stack = new ArrayDeque<>();
        Set<Character> set = new HashSet<>();
        MyComparator comp = new MyComparator();

        int result = 0;
        int remain = tasks.length;
        while (remain > 0) {
            Collections.sort(uniqTasks, comp);
            int i = 0;
            for (; i < uniqTasks.size(); i++) {
                Character task = uniqTasks.get(i);
                if ( freqs[task-'A'] != 0 && ! set.contains(task) ) {
                    set.add(task);
                    stack.offerLast(task);
                    freqs[task-'A']--;
                    remain--;
                    if (stack.size() > n) {
                        Character toPop = stack.pollFirst();
                        set.remove(toPop);
                    }
                    break;
                }
            }

            // No task added; Have to add idle
            if (i == uniqTasks.size()) {
                set.add(' ');
                stack.offerLast(' ');
                if (stack.size() > n) {
                    Character toPop = stack.pollFirst();
                    set.remove(toPop);
                }
            }
            //System.out.println(stack.peekLast() + " " + remain);
            result++;
        }
        return result;
    }
    static class MyComparator implements Comparator<Character>{
        @Override
        public int compare(Character c1, Character c2) {
            if ( freqs[c1-'A'] == freqs[c2-'A'] ) return 0;
            return freqs[c1-'A'] > freqs[c2-'A'] ? -1 : 1;
        }
    }
}
/*
["A","A","A","B","B","B"]
2
["A","A","A","B","B","B"]
3
["A","A","A","B","B"]
4
["A","A","A","B","B","C","D"]
4
["A","A","A","B","B","C","D"]
2
["A","A","A","B","B","C","D"]
9
["A","A","A","B","B","C","D"]
0
["A","A","A"]
0
*/