## DEV Community

Abhishek Chaudhary

Posted on

# Reorganize String

Given a string `s`, rearrange the characters of `s` so that any two adjacent characters are not the same.

Return any possible rearrangement of `s` or return `""` if not possible.

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

Constraints:

• `1 <= s.length <= 500`
• `s` consists of lowercase English letters.

SOLUTION:

``````import heapq

class Solution:
def reorganizeString(self, s: str) -> str:
op = ""
ctr = {}
for c in s:
ctr[c] = ctr.get(c, 0) + 1
heap = [(-n, c) for c, n in ctr.items()]
hlen = len(heap)
heapq.heapify(heap)
while len(heap) > 0:
currn, currc = heapq.heappop(heap)
if currc != op[-1] if len(op) > 0 else True:
op += currc
if currn + 1 < 0:
heapq.heappush(heap, (currn + 1, currc))
else:
if len(heap) == 0:
return ""
nextn, nextc = heapq.heappop(heap)
op += nextc
heapq.heappush(heap, (currn, currc))
if nextn + 1 < 0:
heapq.heappush(heap, (nextn + 1, nextc))
return op
``````