Priority Queue of custom class O(n) time


  • 0
    Q

    It's good to practice priority queue and comparator. The idea is to get the valid characters from priority queue for the highest character count. If there is no valid character but not finished, then return ""
    Use another linked list to hold all the invalid characters at the moment and pop it back to priority queue when it become valid next pass

    Time = O(n*log_2(26)) = O(n) where n is the length of string

    public class Solution {
        // character and count pairs
        class CharCnt {  
            char c;
            int cnt;
            public CharCnt(char c, int cnt) {
                this.c = c;
                this.cnt = cnt;
            }
        } 
        public String rearrangeString(String str, int k) {
            int[] cMap = new int[26];  
            char[] sArray = str.toCharArray();
            // count all the characters
            for (int i = 0; i < sArray.length; ++i) {   
                cMap[sArray[i]-'a']++;
            }
            // compare character count, see below
            Comparator<CharCnt> comparator = new CharCntComparator();  
            PriorityQueue<CharCnt> p = new PriorityQueue<CharCnt>(comparator);
            // time O(1)
            for (int i = 0; i < 26; ++i) {
                if (cMap[i] > 0) {
                    p.add(new CharCnt((char)(i+'a'),cMap[i]));
                }
            }
            LinkedList<CharCnt> kList = new LinkedList<CharCnt>();
            StringBuilder sb = new StringBuilder();
            while (!p.isEmpty()) {
                CharCnt tmp = p.poll();
                // append valid character with most count
                sb.append(tmp.c);   
                tmp.cnt -= 1;
                // make it invalid for k rounds
                kList.addLast(tmp); 
                if (sb.length() >= k) {
                    // pop the head of the list and put it back to queue
                    CharCnt tcc = kList.pollFirst();  
                    if (tcc != null && tcc.cnt != 0) {
                        p.add(tcc);
                    }
                }
            }
            // check if the work finished
            while (kList.size() > 0) {  
                if (kList.pollFirst().cnt != 0) {
                    return "";
                }
            }
            return sb.toString();  
        }
        class CharCntComparator implements Comparator<CharCnt> {
            @Override
            public int compare(CharCnt x, CharCnt y) {
                return y.cnt-x.cnt;
            }
        }
    }

Log in to reply
 

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