358. Rearrange String k Distance Apart K 距离间隔重排字符串

作者： 负雪明烛 id： fuxuemingzhu 个人博客： https://fuxuemingzhu.cn/

---

题目地址: https://leetcode.com/problems/rearrange-string-k-distance-apart

题目描述：

Given a non-empty string str and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Example 1:

str = " ", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.

Example 2:

str = "aaabc", k = 3

Answer: ""

It is not possible to rearrange the string.

Example 3:

str = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

The same letters are at least distance 2 from each other.

题目大意

判断给出的字符串能不能构成一个新的排列，在这个排列中，所有的相同字符之间的间距最少是k.

解题方法

使用Counter统计每个字符出现的次数，然后使用大根堆，每次弹出出现次数最多的字符，添加到生成结果字符串的末尾。如果剩余的不同字符个数不够k，那么说明不能满足题目的要求，返回空字符串。另外，每次弹出出现次数最多的字符之后，不能直接放入堆中，因为直接放入堆中可能下次又被弹出来，所以应该放入一个临时的数组中，在单次操作结束之后再重新插入堆中。

时间复杂度是O(N)，空间复杂度是O(N)。

class Solution:
  def rearrangeString(self, words, k):
    _len = len(words)
    words_count = collections.Counter(words)
    que = []
    heapq.heapify(que)
    for w, v in words_count.items():
      heapq.heappush(que, (-v, w))
    res = ""
    while que:
      cnt = min(_len, k)
      used = []
      for i in range(cnt):
        if not que:
          return ""
        v, w = heapq.heappop(que)
        res += w
        if -v > 1:
          used.append((v + 1, w))
        _len -= 1
      for use in used:
        heapq.heappush(que, use)
    return res

参考资料：

http://www.cnblogs.com/grandyang/p/5586009.html

日期

2018 年 10 月 13 日 —— 这个题没有用OJ测试