<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:
        freq = Counter(s)

        if len(freq) == 0:
            return ""

        pq = [(-value,key) for key,value in freq.items()]
        heapq.heapify(pq)
        result = []
        p_a, p_b = 0, ""
        while pq:
            a, b = heapq.heappop(pq)
            #a = -2 , b = a
            result += b #ab

            if p_a < 0:
                heapq.heappush(pq, (p_a,p_b))

            a += 1
            p_a, p_b = a, b
        
        if len(result) == len(s):
            return "".join(result)
        return ""

        


                






        
        
        
16700