We need to rearrange the characters of a string so that no two identical characters sit next to each other. If that is not possible, we return an empty string.

The first question to ask is: when is it impossible? Consider the string "aaab". We have three as and one b. Even if we place b between two as, we get "aaba" which still has adjacent as. There just are not enough non-a characters to separate all the as.

The key observation is this: if any character appears more than (n + 1) / 2 times (where n is the string length), it is impossible to rearrange. Think of it as placing characters into alternating slots. For a string of length n, the even positions (0, 2, 4, ...) can hold at most ceil(n/2) characters. If the most frequent character exceeds that count, it must spill into adjacent positions, violating the constraint.

Key Constraints:

Intuition

The most natural first thought: if we want to spread characters apart, we should deal with the most frequent characters first. They are the hardest to place since they need the most "breathing room."

Here is the idea. Sort all characters by their frequency in descending order. Then fill them into the result array at even indices first (0, 2, 4, ...), and once those are full, continue at odd indices (1, 3, 5, ...). Since we process characters from most frequent to least frequent, the dominant character gets placed at even positions where no two are adjacent. The remaining characters fill in the gaps.

Before doing any of this, we check the impossibility condition: if any character appears more than (n + 1) / 2 times, return "".

Algorithm

Example Walkthrough

Code

The sorting step here is O(k log k) where k = 26, which is effectively constant. But what if we want a more flexible approach that does not rely on filling even/odd indices? The max heap approach gives us a more intuitive greedy strategy: at each step, pick the most frequent character that is different from the one we just placed.

Intuition

Instead of pre-sorting and filling indices, what if we built the string one character at a time, always choosing the best character to place next?

The greedy insight: at each position, place the character with the highest remaining frequency, as long as it is not the same as the character we just placed. This maximizes our options going forward. If we always "use up" the most common character whenever we can, we avoid a situation where we are stuck with too many copies of one character at the end.

Here is the trick that makes this work cleanly with a heap: after placing a character, do not push it back into the heap immediately. Hold it aside for one round. On the next iteration, push it back (with decremented count) before popping the next character. This "hold one back" mechanism guarantees we never place the same character twice in a row.

Algorithm

Example Walkthrough

Code

The heap approach is elegant and generalizable, but we are maintaining a heap for at most 26 characters. Can we skip the heap entirely? If we just count frequencies and fill indices directly, we avoid both sorting and heap operations, reaching a truly simple O(n) solution.

Intuition

Here is the simplest way to think about this problem. We have a result array with positions 0 through n-1. If we fill positions 0, 2, 4, ... first and then 1, 3, 5, ..., any two consecutive characters we place are two indices apart in the result. They can never be adjacent.

So the strategy is dead simple:

The only constraint is that the most frequent character must fit within the even positions (plus possibly wrapping to some odd positions). This is guaranteed as long as its frequency does not exceed (n + 1) / 2.

Algorithm

Example Walkthrough

Code