Leetcode 767 Reorganize String

Return any possible rearrangement of s or return "" if not possible.

Input: s = "aab"
Output: "aba"

Input: s = "aaab"
Output: ""

• We use max heap to solve this question. We need to calculate the frequence of each letter. The we store the letter and frequence as pair based on its frequence in max heap and we pop the first letter and frequence pair from heap as the pre pair and append the letter to result string. We iterate the heap, pop the letter and frequence pair from heap as current pair. We append the current letter to result string and update pre pair’s frequence to minus 1. Now if the pre letter frequence is not 0, we re-push the letter with updated frequence pair to heap and let the pre pair now equal to current pair until there is nothing in heap. If the result string is not equal to the length of given string return ‘’ otherwise return result string.

class Solution:
    def reorganizeString(self, S: str) -> str:
            if not S: return "" 
            # create a counter 
            heap = []
            for key, value in collections.Counter(S).items():
                heapq.heappush(heap,[-value,key])

            res = ""
            pre = heapq.heappop(heap)
            res+= pre[1]

            while heap: 
                curr = heapq.heappop(heap)
                res+=curr[1]

                pre[0]+=1
                if pre[0]<0:
                    heapq.heappush(heap,pre)
                pre = curr 

            return "" if len(res)!=len(S) else res