Untitled

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        res = ""

        # define q
        q = collections.deque([])

        # generate maxHeap
        counter = Counter(s) # outputs dictionary of occur counts
        # ONLY MINHEAP in python - just negative the value to get around this, we want to sort by value first as welll
        max_heap = [ (-value, key) for key, value in counter.items() ]
        heapq.heapify(max_heap)

        while max_heap:
            value, key = heapq.heappop(max_heap)

            res += key
            # add to q to wait k iterations before use again
            if value + 1 != 0: 
                q.append((key, value + 1, len(res) - 1)) # we increment cause negative value

            # can we re-add from our queue to our max heap
            if q:
                # peak front of queue
                q_key, q_value, q_index = q[0]
                if len(res) - k >= q_index:
                    q.popleft()
                    heapq.heappush(max_heap, (q_value, q_key))

        return res if len(res) == len(s) else ""