Use a max-heap of (count, char). At each step, pop the most frequent character and add it to result. Then pop the second most frequent and add it. Push both back (with decremented counts) if they still have remaining occurrences. It ensures the most frequent characters are spread out. Time: . Space: . The two-pop pattern ensures you never pick the same character twice in a row.
If only one character remains in the heap and it has count , it is impossible to place without adjacency. The heap maintains the greedy priority automatically.