Java 7 version of PriorityQueue O(nlogn) with comments and explanations


  • 51

    The greedy algorithm is that in each step, select the char with highest remaining count if possible (if it is not in the waiting queue). PQ is used to achieve the greedy. A regular queue waitQueue is used to "freeze" previous appeared char in the period of k.

    In each iteration, we need to add current char to the waitQueue and also release the char at front of the queue, put back to maxHeap. The "impossible" case happens when the maxHeap is empty but there is still some char in the waitQueue.

    public class Solution {
        public String rearrangeString(String str, int k) {
            
            StringBuilder rearranged = new StringBuilder();
            //count frequency of each char
            Map<Character, Integer> map = new HashMap<>();
            for (char c : str.toCharArray()) {
                if (!map.containsKey(c)) {
                    map.put(c, 0);
                }
                map.put(c, map.get(c) + 1);
            }
            
            //construct a max heap using self-defined comparator, which holds all Map entries, Java is quite verbose
            Queue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>() {
                public int compare(Map.Entry<Character, Integer> entry1, Map.Entry<Character, Integer> entry2) {
                    return entry2.getValue() - entry1.getValue();
                }
            });
            
            Queue<Map.Entry<Character, Integer>> waitQueue = new LinkedList<>();
            maxHeap.addAll(map.entrySet());
            
            while (!maxHeap.isEmpty()) {
                
                Map.Entry<Character, Integer> current = maxHeap.poll();
                rearranged.append(current.getKey());
                current.setValue(current.getValue() - 1);
                waitQueue.offer(current);
                
                if (waitQueue.size() < k) { // intial k-1 chars, waitQueue not full yet
                    continue;
                }
                // release from waitQueue if char is already k apart
                Map.Entry<Character, Integer> front = waitQueue.poll();
                //note that char with 0 count still needs to be placed in waitQueue as a place holder
                if (front.getValue() > 0) {
                    maxHeap.offer(front);
                }
            }
            
            return rearranged.length() == str.length() ? rearranged.toString() : "";
        }
        
    }

  • 0
    B

    Very nice solution. I've wrote a python version. However, it is ETL. Anyone can help me take a look at it?

    import heapq
    from collections import deque
    class Solution(object):
        def rearrangeString(self, str, k):
            """
            :type str: str
            :type k: int
            :rtype: str
            """
            if k == 0:
                return str
            result = ""
            maxHeap = []
            m = {} #char to count map
            for s in str:
                m[s] = m.get(s, 0) + 1
            # python's heapq is min heap by default. So create a customized heap order is to have each element on the heap to be a tuple. The first tuple element is the one will be accpeted to be normal python comparisons. Assign the count value to be negative, so that the heap to be a max heap.
            for key,value in m.items():
                heapq.heappush(maxHeap, (-1*value,key))
            
            waitQueue = deque()
            
            while len(maxHeap) > 0:
                current = heapq.heappop(maxHeap)
                result += current[1]
                # current[0] -= 1 tuple is immutable, cannot assign value 
                new_current = (-1 * current[0] - 1, current[1])
                waitQueue.append(new_current)
                
                if len(waitQueue) < k:
                    continue
                front = waitQueue.popleft()
                if front[0] > 0:
                    heapq.heappush(maxHeap, (-1*front[0], front[1]))
                    
            return result if len(result) == len(str) else ""

  • 1
    B

    Shouldn't the initial value in the map be 1?
    if (!map.containsKey(c)) {
    map.put(c, 1); <------------- here
    }


  • 0

    that is not "if else", map.put(c, map.get(c) + 1); will always be executed


  • 1
    E

    Is the size of the heap at most 26? You can make the log(n) part just constant.


  • 1

    @xuyirui Can you help me figure out why my code can not pass? Thanks.

    public class Solution {
        public String rearrangeString(String str, int k) {
            if (k == 0) {
                return str;
            }
            
            HashMap<Character, Integer> map = new HashMap<Character, Integer>();
            for (char c : str.toCharArray()) {
                if (!map.containsKey(c)) {
                    map.put(c, 1);
                } else {
                    map.put(c, map.get(c) + 1);
                }
            }
            
            PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<Map.Entry<Character, Integer>>(10, new Comparator<Map.Entry<Character, Integer>>() {
                public int compare(Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) {
                    return b.getValue() == a.getValue() ? a.getKey() - b.getKey() : b.getValue() - a.getValue();
                }
            });
            for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                queue.offer(entry);
            }
            char[] result = new char[str.length()];
            int index = 0;
            int len = result.length;
            List<Map.Entry<Character, Integer>> list = null;
            while (!queue.isEmpty()) {
                int min = Math.min(k, len);
                list = new ArrayList<Map.Entry<Character, Integer>>();
                for (int i = 0; i < min; i++, len--) {
                    if (queue.isEmpty()) {
                        return "";
                    }
                    Map.Entry<Character, Integer> curr = queue.poll();
                    result[index++] = curr.getKey();
                    curr.setValue(curr.getValue() - 1);
                    if (curr.getValue() > 0) {
                        list.add(curr);
                    }
                }
                for (Map.Entry<Character, Integer> entry : list) {
                    queue.offer(entry);
                }
            }
            return String.valueOf(result);
        }
    }
    

  • 1

    @xuyirui Can you tell more about why: //note that char with 0 count still needs to be placed in waitQueue as a place holder


  • 0

    Good idea about the wait queue.


  • 3
    A

    I think the running time is O(Nlog26) rather than O(NlogN). Because the max size of heap is 26


  • 4
    A

    It should be O(n) because there are at most 26 elements in the priority queue and thus polling from pq is O(1)


  • 0
    J

    @bing28 For the result, use a list to record all the character, then use join to create a string. Otherwise, there will be ETL


  • 0
    L

    Simple and straightforward solution! Thanks!


  • 2

    The idea of using two Queue is brilliant! By polling entries from the PriorityQueue which are used to construct our result, and offering to queue which served as ensuring the distance larger than K, we can keep recording all the entries and thses entries are "transfered" between two queues. The idea is fantastic.


  • 3

    @Tōsaka-Rin Agreed! Here's my somewhat terse java8 solution based on @shuxu's answer:

    public String rearrangeString(String s, int k) {
    
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
        PriorityQueue<Map.Entry<Character, Integer>> pq = 
           new PriorityQueue<>((x, y) -> Integer.compare(y.getValue(), x.getValue()));
        pq.addAll(map.entrySet());
        Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
        StringBuilder res = new StringBuilder();
    
        while (!pq.isEmpty()) {
              Map.Entry<Character, Integer> curr = pq.poll();
              res.append(curr.getKey());
              curr.setValue(curr.getValue() - 1);
              queue.offer(curr);
              if (queue.size() < k)
                    continue;
              Map.Entry<Character, Integer> front = queue.poll();
              if (front.getValue() > 0)
                    pq.offer(front);
        }
        return res.length() == s.length() ? res.toString() : "";
    }      
    

  • 1
    G

    Have one question.
    If I do not use the StringBuilder but use the String.

    String res = "";
    for each step: res += char;
    

    This will cause TLE. But I do not know why.


  • 0
    N

    @gggggo i have the same problem, maybe it's much faster to use stringbuilder.


  • 2
    S

    @gggggo It is because when you use plain concatenation, each time you do "+" a StringBuilder object is created the first string is appended and then the next and it is copied back to the first. So this is more costly than using one StringBuilder Object. Hope it helps.

    https://stackoverflow.com/questions/18453458/string-builder-vs-string-concatenation


  • 1
    Z

    @CodingSlug use b.getValue().equals(a.getValue()) instead of b.getValue() == a.getValue()


  • 0
    M

    I prefer this solution to the highest upvoted post. Although that one is significantly faster for this problem, it would easily allure the interviewer to challenge you with a follow-up on how to handle the situation when k is extremely large.


  • 0
    G

    Nice idea by using wait queue to achieve k distance requirement.


Log in to reply
 

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