358.K距离间隔重排字符串.py

# 给你一个非空的字符串 s 和一个整数 k，你要将这个字符串中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离至少为 k。
#
# 所有输入的字符串都由小写字母组成，如果找不到距离至少为 k 的重排结果，请返回一个空字符串 ""。
#
# 示例 1：
#
# 输入: s = "aabbcc", k = 3
# 输出: "abcabc"
# 解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。
# 示例 2:
#
# 输入: s = "aaabc", k = 3
# 输出: ""
# 解释: 没有办法找到可能的重排结果。
# 示例 3:
#
# 输入: s = "aaadbbcc", k = 2
# 输出: "abacabcd"
# 解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        from collections import Counter
        import heapq
        if k <= 1: return s
        c = Counter(s)
        n = len(s)
        heap = [(-v, k) for k, v in c.items()]
        heapq.heapify(heap)
        res = ""
        while heap:
            tmp = []
            for _ in range(k):
                if not heap:return res if len(res) == n else ""
                num, alp = heapq.heappop(heap)
                num += 1
                res += alp
                if num != 0:
                    tmp.append((num, alp))
            for t in tmp:
                heapq.heappush(heap, t)
        return res