<p>Given a string <code>s</code>, rearrange the characters of <code>s</code> so that any two adjacent characters are not the same.</p>

<p>Return <em>any possible rearrangement of</em> <code>s</code> <em>or return</em> <code>&quot;&quot;</code> <em>if not possible</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "aab"
<strong>Output:</strong> "aba"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "aaab"
<strong>Output:</strong> ""
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 500</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def reorganizeString(self, s: str) -> str:
        cnt = Counter(s)
        heap = []
        for k, v in cnt.items():
            heapq.heappush(heap, [-v, k])

        result = ""
        while heap:
            # print(heap)
            if len(heap) == 1 and -heap[0][0] > 1:
                return ""
            n1, c1 = heapq.heappop(heap)
            n2, c2 = heapq.heappop(heap) if heap else [0, ""]
            result += c1 + c2
            if -n1 - 1 > 0:
                heapq.heappush(heap, [n1 + 1, c1])
            if -n2 - 1 > 0:
                heapq.heappush(heap, [n2 + 1, c2])
        
        return result
16200