My Python solution using max heap and deque is ETL. Help wanted.


  • 0
    B

    My solution is inspired by this post. https://leetcode.com/discuss/108212/java-version-priorityqueue-nlogn-with-comments-explanations

    The "impossible" case happens when the maxHeap is empty but there is still some char in the waitQueue.

    I try to implement it in python. It is a working solution. However, it exceeds the time limit. And I don't know how to optimize it. Any help will be appreciate.

    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

    This is a nice solution. I believe the one thing you have to change to reduce the run time significantly is how you do string concatenation. As strings are immutable, every time you use "+" to append to the end, you are creating a new string. Therefore you end up with O(n^2) time. I tried your code with the minor change of making result a list and calling ''.join(result) at the end to return the string, it passed the tests.

    One more possible improvement I noticed along the way:
    You could store the counts in m with a minus sign, and call heapq.heapify to generate the max heap. heapify actually runs in O(n) time if I recall correctly while your method does it in O(nlogn) time. What heapify does is that it forms the heap structure from the bottom level up, you can google for more details if you like.


  • 1
    S

    hi, there, you can simplify you code in this way:

        heap=[]
        c=collections.Counter(str)
        for key, val in c.items():
            heapq.heappush(heap, (-1*val, key))
        
        q=collections.deque([])
        res=[]
        while heap:
    
            v, key=heapq.heappop(heap)
            res.append(key)
            q.append( (v+1, key))
    
            if len(q)<k:
                continue
            v, key=q.popleft()
            
            if v<0:
                heapq.heappush(heap, (v, key))
          
        tmp=''.join(res)
        return tmp if len(tmp)==len(str) else ''

Log in to reply
 

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