The greedy approach: always place the most frequent remaining character, as long as it differs from the previous character. Use a max-heap ordered by character frequency.
Pop the most frequent, append it to result. Before pushing it back, place the character you used last time (if any) back in the heap.
It ensures you never place the same character twice in a row, and you always use the most frequent available option. Time: . Space: .