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

        total_chars = sum(alpha.values())
        max_freq = max(alpha.values())
        if max_freq > (total_chars + 1) // 2:
            return ""

        sorted_chars = sorted(alpha.items(), key=lambda x: -x[1])
    
        result = []
        prev_char, prev_freq = None, 0
        
        while sorted_chars:
            char, freq = sorted_chars.pop(0)
            result.append(char)
            freq -= 1
            
            if prev_freq > 0:
                sorted_chars.append((prev_char, prev_freq))
                sorted_chars = sorted(sorted_chars, key=lambda x: -x[1])
            
            prev_char, prev_freq = char, freq
        
        return ''.join(result)
16100