Q71: Reorganize String. - DSA Patterns (Multi-Lang)

In Simple Words: Max-Heap by frequency. Always pop the most frequent character, append it, but hold it in prev so it cannot be placed consecutively. Re-insert prev on next step.

Time: $O(N \log 26) = O(N)$ | Space: $O(26) = O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

import heapq
from collections import Counter

def reorganizeString(s: str) -> str:
    count = Counter(s)
    max_heap = [[-c, char] for char, c in count.items()]
    heapq.heapify(max_heap)
    res = []
    prev = None
    while max_heap or prev:
        if prev and not max_heap:
            return ""
        cnt, char = heapq.heappop(max_heap)
        res.append(char)
        cnt += 1  # decrease frequency since count is negative
        if prev:
            heapq.heappush(max_heap, prev)
            prev = None
        if cnt < 0:
            prev = [cnt, char]
    return "".join(res)