<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 {
public:
    string reorganizeString(string s) {
        // TC:  O(n*logk) SC: O(k) to store the counters
        // Keep the char count in the vector
        vector<int> charCount(26, 0);
        for(char c : s) {
            charCount[c - 'a']++;
        }

        // Max heap by char count
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < 26; i++) {
            if (charCount[i] > 0)
                // Pair of char count with ascii value of char
                pq.push({charCount[i], i + 'a'});
        }

        string result;
        while (! pq.empty()) {
            // Pop the first char
            auto [chrCount, asciiChr] = pq.top();
            pq.pop();
            // Check for result emptiness or the current char is not
            // the same the previous character
            if (result.empty() || asciiChr != result.back()) {
                // append the char to the result
                result += char(asciiChr);
                // decrement the char counter by 1 and insert back into heap
                if(--chrCount > 0)
                    pq.push({chrCount, asciiChr});
            } else { // if the char is the same as the prev one
                if (pq.empty()) {   // if the heap is empty return empty
                    return "";
                }
                // pop the second char
                auto [altChrCount, altAsciiChr] = pq.top();
                pq.pop();
                // add it to the result
                result += char(altAsciiChr);
                // decrement the second char by 1
                if (--altChrCount > 0)
                    pq.push({altChrCount, altAsciiChr});
                // push back the first 
                pq.push({chrCount, asciiChr});
            }

        }
        return result;
    }
};
8500