Reorder a tape so no symbol repeats adjacently

Question

Given a multiset of symbols, produce any arrangement in which no two adjacent symbols are equal. If no such arrangement exists, return the empty string.

symbols = "AAB"
-> "ABA"           # no two neighbors match
symbols = "AAAB"
-> ""              # A occurs too often to separate

Return a valid rearrangement, or "" if impossible. Aim for $O(n \log u)$ .

Accepted Answer

Always place the most frequent remaining symbol that is not the one just placed. A max-heap keyed by remaining count gives the current most frequent in O(\log u). After placing a symbol, hold it aside for one step so it cannot be chosen again immediately; reinsert it on the next iteration once its count is updated. If at some point the only available symbol is the one just placed, the arrangement is impossible. Tracing "AAB": place A, hold it; place B, return A to the heap; place A again, yielding "ABA". For "AAAB", A (count 3) cannot be spaced out among only four slots, so the heap empties e…

Reorder a tape so no symbol repeats adjacently

Your answer

More Coding questions