16-Line Python Solution using heapq, collections.Counter


  • 0
    class Solution(object):
        def rearrangeString(self, str, k):
            wordlist = [(-n,c) for (c,n) in collections.Counter(str).items()]
            heapq.heapify(wordlist)
            ans, temp = [], []
            while len(ans) < len(str):
                while temp:
                    heapq.heappush(wordlist, temp.pop())
                for _ in xrange(max(k,1)):
                    if not wordlist and temp:
                        return ''
                    if wordlist:
                        n, c = heapq.heappop(wordlist)
                        ans.append(c)
                        n += 1
                        if n < 0:
                            temp.append((n,c))
            return ''.join(ans)

Log in to reply
 

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