Leetcode 778 Solution

This article provides solution to leetcode question 778 (reorganize-string)
Categories:
Tags:
Access this page by simply typing in "lcs 778" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/reorganize-string

Solution

class Solution:
    def reorganizeString(self, s: str) -> str:
        cnts = collections.defaultdict(int)
        for ch in s:
            cnts[ch] += 1

        q = []
        for ch, cnt in cnts.items():
            heapq.heappush(q, (-cnt, ch))

        ans = ""
        while q:
            pending_chars = []

            for _ in range(2):
                if not q:
                    if len(ans) != len(s):
                        return ""
                    else:
                        break

                cnt, ch = heapq.heappop(q)
                cnt = -cnt

                ans += ch

                if cnt - 1 > 0:
                    pending_chars.append((ch, cnt - 1))

            for ch, cnt in pending_chars:
                heapq.heappush(q, (-cnt, ch))

        return ans