My solution is inspired by this post. https://leetcode.com/discuss/108212/java-version-priorityqueue-nlogn-with-comments-explanations

The "impossible" case happens when the maxHeap is empty but there is still some char in the waitQueue.

I try to implement it in python. It is a working solution. However, it exceeds the time limit. And I don't know how to optimize it. Any help will be appreciate.

```
import heapq
from collections import deque
class Solution(object):
def rearrangeString(self, str, k):
"""
:type str: str
:type k: int
:rtype: str
"""
if k == 0:
return str
result = ""
maxHeap = []
m = {} #char to count map
for s in str:
m[s] = m.get(s, 0) + 1
# python's heapq is min heap by default. So create a customized heap order is to have each element on the heap to be a tuple. The first tuple element is the one will be accpeted to be normal python comparisons. Assign the count value to be negative, so that the heap to be a max heap.
for key,value in m.items():
heapq.heappush(maxHeap, (-1*value,key))
waitQueue = deque()
while len(maxHeap) > 0:
current = heapq.heappop(maxHeap)
result += current[1]
# current[0] -= 1 tuple is immutable, cannot assign value
new_current = (-1 * current[0] - 1, current[1])
waitQueue.append(new_current)
if len(waitQueue) < k:
continue
front = waitQueue.popleft()
if front[0] > 0:
heapq.heappush(maxHeap, (-1*front[0], front[1]))
return result if len(result) == len(str) else ""
```