Java 2 Queue solution O(n) (fixed size heap)


  • 0
    A

    queue gives us the char with the highest priority by number of times we have to place him
    waiting is a queue for the letters we are not allowed to reuse right now

    Since queue is fixed size in this task the complexity is O(n). So it would be possible to just iterate all remaining letters for same complexity. If you generalize the idea to any char then this solution is better with O(nlogn) vs a O(n^2) standard implementation.

        public String rearrangeString(String s, int k) {
            char[] str = s.toCharArray();
            Map<Character, Letter> letters = new HashMap<>();
            for(char chr : str) {
                letters.put(chr, letters.getOrDefault(chr, new Letter(0, chr)));
                letters.get(chr).time++;
            }
            Queue<Letter> queue = new PriorityQueue<>(26, (a,b) -> -Integer.compare(a.time, b.time));
            queue.addAll(letters.values());
            Queue<Letter> waiting = new LinkedList<>();
            int count = 0;
            while(!queue.isEmpty()) {
                Letter current = queue.poll();
                str[count] = current.name;
                current.time--;
                waiting.add(current.time > 0? current : null);
                if (waiting.size() >= k) {
                    Letter waiter = waiting.poll();
                    if (waiter != null && waiter.time > 0) {
                        queue.add(waiter);
                    }
                }
                count++;
            }
            return count == str.length? new String(str) : "";
        }
        
        private class Letter {
            int time;
            char name;
            public Letter(int time, char name) {
                this.name = name;
                this.time = time;
            }
        }
    

Log in to reply
 

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