<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:
        # hash map

        count = Counter(s) # shorter form of defaultdict and count inc
        # print(count)

        # if most freq (max freq) > half of string len -> impossible
        def possible(count):
            c = max(dict(count).values())
            if (len(s) + 1)//2 < c:
                return False
            return True

        # lets use a pq (max heap) to construct
        def construct():

            pq = []
            for k in count:
                heapq.heappush(pq, [-count[k], k])

            elem = heapq.heappop(pq)
            newS = elem[1]
            # if elem[0] > 0:
            elem[0] += 1

            while pq:
                newElem = heapq.heappop(pq)
                if elem[0] < 0:
                    heapq.heappush(pq, elem)
                elem = newElem
                newS += elem[1]
                elem[0] += 1

            return newS

        if possible(count):
            return construct()

        return ""

16600