Reorganize String Gaps
Problem
Rearrange the letters of a string so that no two neighbours are the same letter. Return any arrangement that works, or the empty string when no arrangement exists.
Examples
Input: s = "aab"
Output: "aba"
Why: the two a's are separated by the bInput: s = "aaab"
Output: ""
Why: three a's cannot be kept apart by a single bInput: s = "vvvlo"
Output: "vlvov"
Why: the three v's are spaced out by the other two lettersHints
0 / 3
Whether an answer exists at all depends only on the counts, not on the original order. Work out which count makes it impossible.
Placing a rare letter early is wasteful: the letter most likely to get stuck at the end is the most frequent one.
Always place the most frequent letter that is not the one you just placed. Hold the letter you used back for exactly one position, then return it to the pool, so it can never land beside itself.
Solution
A max-heap on remaining counts always hands you the letter most at risk of bunching up, and holding the letter you just placed out of the heap for exactly one step is what stops it repeating. The construction is optimal, so failure is detectable without a separate count check: if it ever runs dry before the output is full, no arrangement exists. Time is O(n log d) for d distinct letters, space O(d).
import heapq
from collections import Counter
def reorganize(s):
heap = [(-n, ch) for ch, n in Counter(s).items()]
heapq.heapify(heap) # max-heap on remaining count
out, held = [], None
while heap:
n, ch = heapq.heappop(heap) # most frequent letter still allowed
out.append(ch)
if held:
heapq.heappush(heap, held) # the previous letter is free again
held = (n + 1, ch) if n + 1 else None
return "".join(out) if len(out) == len(s) else ""
print(reorganize("aab")) # -> aba
print(reorganize("aaab")) # -> (empty string)
print(reorganize("vvvlo")) # -> vlvovStuck on the idea rather than the code? Reorganize a String covers it.