LeetCode: 358. Rearrange String k Distance Apart

 

Greedy solution with heap & deque

- append character with 'max frequency' currently

- put the appended character to a deque for cool-down

from collections import Counter, deque
import heapq
class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k <= 1:
            return s
        
        c = Counter(s)
        h = [(-freq, char) for char, freq in c.items()]
        heapq.heapify(h)
        q = deque()

        ret = []
        while h:
            freq, char = heapq.heappop(h)
            freq *= -1
            ret.append(char)
            q.append((freq-1, char))
            if len(q) >= k:
                freq, char = q.popleft()
                if freq >= 1:
                    heapq.heappush(h, (-freq, char))
        return ''.join(ret) if len(ret) == len(s) else ""