We take a greedy approach, using a heap to choose the letter with highest frequency count. We use a queue to store last `k`

characters so we know which character can be put back into the heap to be chosen again.

```
class Solution(object):
def rearrangeString(self, s, k):
count,ans = collections.Counter(s),[]
heap,q = [(-cnt,c) for c,cnt in count.items()],collections.deque()
heapq.heapify(heap)
while heap:
cnt,c = heapq.heappop(heap)
ans += c,
q.append((cnt+1,c))
if len(q) >= k:
t = q.popleft()
if t[0] < 0:
heapq.heappush(heap,t)
return "".join(ans) if len(ans)==len(s) else ""
```