Short Python beats 90%


  • 0

    We take a greedy approach, using a heap to choose the letter with highest frequency count. We use a queue to store last k characters so we know which character can be put back into the heap to be chosen again.

    class Solution(object):
        def rearrangeString(self, s, k):
            count,ans = collections.Counter(s),[]
            heap,q = [(-cnt,c) for c,cnt in count.items()],collections.deque()
            heapq.heapify(heap)
            while heap:
                cnt,c = heapq.heappop(heap)
                ans += c,
                q.append((cnt+1,c))
                if len(q) >= k:
                    t = q.popleft()
                    if t[0] < 0:
                        heapq.heappush(heap,t)
            return "".join(ans) if len(ans)==len(s) else ""

Log in to reply
 

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