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

## # 题目描述：

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

It is not possible to rearrange the string.
``````

Example 3:

``````str = "aaadbbcc", k = 2

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

## # 解题方法

``````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测试