leetcode/reorganizeString.py at main · h66guo/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import heapq
class Solution:
    def reorganizeString(self, s: str) -> str:
        d={}
        for element in s:
            if element in d:
                d[element]+=1
            else:
                d[element]=1
        l=[]
        for element in d:
            temp= [-d[element],element]
            l.append(temp)

        heapq.heapify(l)

        ans=""

        while len(l)>1:
            temp1= heapq.heappop(l)
            temp2=heapq.heappop(l)
            ans+=temp1[1]
            ans+=temp2[1]

            if temp1[0]!=-1:
                heapq.heappush(l, [temp1[0]+1, temp1[1]])


            if temp2[0]!=-1:
                heapq.heappush(l, [temp2[0]+1, temp2[1]])

        if len(l)==0:
            return ans

        if l[0][0]==-1:
            temp=l.pop()
            ans+=temp[1]
            return ans

        else:
            return ""