8.21 - hard - 74

358. Rearrange String k Distance Apart

这道题就是把所有值都进行最大区分，在重新加入heap的时候要注意，如果两个值有同样的count，那么后访问过的要先加进去，比如说bba, size=1，先加入b，此时a,b的count都是1，这时候要先加入a，再加入b

class Solution(object):
    def rearrangeString(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        if k == 0:
            return s
        h = {}
        for c in s:
            h[c] = h.get(c, 0) + 1
        
        heap = []
        for key, val in h.iteritems():
            heapq.heappush(heap, [-val, key])
        
        res = []
        
        while heap:
            temp = []
            n = len(s) - len(res)
            for _ in range(min(k, n)):
                if not heap:
                    return ""
                cur_val, key = heapq.heappop(heap)
                res.append(key)
                cur_val += 1
                if cur_val != 0:
                    temp.append([cur_val, key])
            
            while temp:
                heapq.heappush(heap, temp.pop())
        
        return "".join(res)