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 -
sconsists 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
Top comments (0)