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