Got a very ugly solution here, need some advise.(PriorityQueue, HashMap and greedy)


  • 0
    F

    The idea is very straightforward:
    Use a hashmap to get the frequency of each character, then use a priorityqueue to get ascending order of these character by their frequencies.
    In the while loop, basically I use two pointers to track the correct bucket for the next character: one is 'i' moving from head to tail and the other is the index of the current character(this index is gotten from the last time we encounter the character). We repeatedly go through this process, until all the characters in the string are processed or an impossible input.
    Many places in my code are not beautiful, like I have to use another class to store the character information and I used an array(ans) to store the final answer. Need some suggestions here.
    Thank you, all, very much.

    public class Solution {
        public String rearrangeString(String str, int k) {
            int length = str.length();
            char[] ans = new char[length];
            Node[] nodes = new Node[26];
            for(int i = 0; i < length; i++){
                if(nodes[str.charAt(i)-'a'] == null){
                    nodes[str.charAt(i)-'a'] = new Node(str.charAt(i), 0, 0);
                }
                nodes[str.charAt(i)-'a'].ch = str.charAt(i);
                nodes[str.charAt(i)-'a'].count++;
            }
            PriorityQueue<Node> pq = new PriorityQueue<>(10, new Comparator<Node>(){
                public int compare(Node n1, Node n2){
                    if(n1.count != n2.count)
                        return n2.count-n1.count;
                    return n1.index-n2.index;
                } 
            });
            
            for(Node node : nodes){
                if(node != null)
                    pq.offer(node);
            }
            
            int i = 0;
            while(!pq.isEmpty()){
                Node node = pq.poll();
                if(node.index < i)
                    node.index = i;
                if(node.index >= length) return "";
                ans[node.index] = node.ch;
                node.index += k;
                while(i < length && ans[i] != '\u0000')
                    i++;
                if(--node.count != 0)
                    pq.offer(node);
            }
            StringBuilder sb = new StringBuilder();
            for(char c : ans)
                sb.append(c);
            return sb.toString();
        }
        
        class Node{
            public char ch;
            public int count;
            public int index;
            public Node(char ch, int count, int index){
                this.ch = ch;
                this.count = count;
                this.index = index;
            }
        }
    }```

Log in to reply
 

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