from collections import Counter
from heapq import *

class Solution:
  def rearrangeString(self, str1):
    
    freqs = sorted(list(Counter(str1).items()), key=lambda x: x[1], reverse=True)

    res = ""

    prev_char = None

    while freqs:
      i = 0
      while i < len(freqs):
        char, freq = freqs[i]

        if prev_char and prev_char == char:
          return ""

        res += char
        freqs[i] = (char, freq - 1)

        prev_char = char

        if freqs[i][1] == 0:
          del freqs[i]

        i += 1
        
    return res