Init

1 files changed, 16 insertions, 0 deletions

diff --git a/progs/a402.py b/progs/a402.py
new file mode 100644
index 0000000..c45fd00
--- /dev/null
+++ b/progs/a402.py
@@ -0,0 +1,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 "")
\ No newline at end of file