767. Reorganize String (Python)

Related Topic

Heap.

Description

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Sample I/O

Example 1

Input: S = "aab"
Output: "aba"

Example 2

Input: S = "aaab"
Output: ""

Note

• S will consist of lowercase letters and have length in range [1, 500].

Methodology

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.

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

BigO

Time complexity : O(nlogn) as we construct the heap need to take O(nlogn)