blob: c45fd0079ab36167122692adbaef777a91141e21 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import heapq
from collections import Counter
def rearange_string(S):
ctr = Counter(S)
heap = [(-value, key) for key, value in ctr.items()]
heapq.heapify(heap)
if (-heap[0][0]) * 2 > len(S) + 1:
return ""
ans = []
while len(heap) >= 2:
nct1, char1 = heapq.heappop(heap)
nct2, char2 = heapq.heappop(heap)
ans.extend([char1, char2])
if nct1 + 1: heapq.heappush(heap, (nct1 + 1, char1))
if nct2 + 1: heapq.heappush(heap, (nct2 + 1, char2))
return "".join(ans) + (heap[0][1] if heap else "")
|
