Reorganize String - Implementation

Here is the solution:

function reorganizeString(s)
 count := frequency map of characters
 maxFreq := maximum frequency
 if maxFreq > (length + 1) / 2 then
 return ""
 heap := max-heap of (freq, char)
 for each (char, freq) in count
 heap.push((freq, char))
 result := []
 prev := null
 while heap is not empty
 (freq, char) := heap.pop()
 result.append(char)
 if prev is not null then
 heap.push(prev)
 if freq > 1 then
 prev := (freq - 1, char)
 else
 prev := null
 return join(result)

Time: $O(n \log k)$ where $k$ is alphabet size. Space: $O(k)$.