Here's the heap-based approach.
function reorganizeString(s):
freq = countFrequencies(s)
maxHeap = new MaxHeap() // ordered by frequency
for each (char, count) in freq:
if count > (s.length + 1) / 2:
return ""
maxHeap.push((count, char))
result = []
prev = null
while maxHeap is not empty:
(count, char) = maxHeap.pop()
if prev is not null and prev.count > 0:
maxHeap.push(prev)
result.append(char)
prev = (count - 1, char)
return result joined as string