LC 0767 [M] Reorganize String - ALawliet/algorithms GitHub Wiki
https://www.youtube.com/watch?v=2g_b1aYTHeg
from queue import PriorityQueue
class Solution:
def reorganizeString(self, s: str) -> str:
count = Counter(s)
maxH = PriorityQueue()
for char, cnt in count.items():
maxH.put( [-cnt, char]) # most frequent
# maxHeap = [[-cnt, char] for char, cnt in count.items()]
# heapq.heapify(maxHeap) # O(n)
prev = None # last picked, currently held
res = ''
while not maxH.empty() or prev:
if prev and maxH.empty():
return ''
# most frequent, except prev
cnt, char = maxH.get()
res += char
cnt += 1 # reverse decrement
if prev:
maxH.put(prev)
prev = None
if cnt != 0:
prev = [cnt, char]
return res