The adjacency constraint turns this into a scheduling problem: every copy of a letter is a job that must not run back to back with another copy of itself. The letter with the most copies is the bottleneck — it needs the most separators between its own copies — so the safe order of work is always most frequent first. Place the most frequent remaining letter, then hold it out of the candidate pool for exactly one round so it can never be chosen twice in a row; whichever letter gets picked in between is the separator. A max-heap keeps each most-frequent lookup cheap — the same greedy shape as Task Scheduler with a cooldown of 1.
Brute Force: Try Every Permutation
Time O(n!·n)Space O(n)Generate every ordering of the letters and keep the first one in which no two neighbors are equal. It is guaranteed to find a valid arrangement whenever one exists, because it exhausts the whole space of orderings. But that guarantee is its only virtue: the search has no structure to exploit, checks every candidate from scratch, and re-generates the same ordering many times over whenever a letter repeats.
from itertools import permutations
class Solution: def reorganizeString(self, s: str) -> str: for candidate in permutations(s): ok = True for i in range(len(candidate) - 1): if candidate[i] == candidate[i + 1]: ok = False break if ok: return "".join(candidate) return ""Why it is hopeless: there are up to n! orderings and each one costs an O(n) adjacency scan, giving O(n!·n) time in the worst case. With n capped at 500, this never finishes on real input — 20! already exceeds 10^18. Space stays at O(n) because the generator produces one candidate tuple at a time. Correct, exhaustive, and unusable.
Max-Heap Greedy
OptimalTime O(n log k)Space O(n)Count the letters, then let a max-heap always surface the most frequent ready letter. Each round: pop the top, place it, and reinsert the previous letter, whose one-round rest is over. Holding the just-placed letter out of the heap for exactly one round is the whole trick: the next pick can never be the same letter, so the adjacency constraint becomes automatic. The run either finishes with all n letters placed, or the heap runs dry with one letter still waiting — that wait is exactly the missing separator, and the answer is an empty string.
import heapqfrom collections import Counter
class Solution: def reorganizeString(self, s: str) -> str: counts = Counter(s) # Python heapq is a min-heap, so negative counts give a max-heap. heap = [(-cnt, ch) for ch, cnt in counts.items()] heapq.heapify(heap)
result = [] prev_ch, prev_cnt = None, 0 # last placed letter, held out of the heap
while heap: cnt, ch = heapq.heappop(heap) # most frequent ready letter result.append(ch) if prev_cnt < 0: # the previous letter has finished resting heapq.heappush(heap, (prev_cnt, prev_ch)) prev_ch, prev_cnt = ch, cnt + 1
return "".join(result) if len(result) == len(s) else ""Watch the cooldown slot do its work on s = "aab" — each pick lands a letter different from the previous one because the previous one is resting:
Result
The output string fills here, left to right, one chip per round.
Remaining counts
Max-heap (ready)
leftmost pops next — most frequent first, ties by letter
Cooldown slot
no letter is resting right now
the previous letter always rests one full round in the cooldown slot — that gap is what keeps identical letters apart
Count the letters first: a appears 2 times, b appears 1 time. Every letter starts in the max-heap, keyed on its remaining count, so the most frequent ready letter is always on top (the heap is drawn as pop order: most frequent first, ties by letter). The rule for the whole run: each round pop the top, place it, and hold it in the single cooldown slot for one round. A letter that rests this round is barred from the next pick, so two identical letters can never land side by side.
Now the impossible case, s = "aaab" — watch the heap run dry one round before the string is complete:
Result
The output string fills here, left to right, one chip per round.
Remaining counts
Max-heap (ready)
leftmost pops next — most frequent first, ties by letter
Cooldown slot
no letter is resting right now
the previous letter always rests one full round in the cooldown slot — that gap is what keeps identical letters apart
Setup for the impossible example: a has 3 copies and b has 1. Feasibility math before the run — three copies of a need two other letters sandwiched between them (a _ a _ a), but only one non-a letter exists, so a valid arrangement cannot exist. Formally a letter may appear at most ceil(4 / 2) = 2 times in a 4-char string. The greedy will discover the dead end on its own; watch where it gets stuck.
Correctness: every placed letter was popped from the heap, and the letter placed in the previous round is resting in the cooldown slot rather than in the heap, so consecutive placements always differ. Failure has exactly one shape: the heap empties while a letter still has copies, meaning that letter can no longer sit next to anything but itself. That can only happen when some letter appears more than ceil(n / 2) times — k copies need k − 1 separators between them, but only n − k other letters exist. When no letter exceeds that budget (k − 1 is at most n − k, i.e. k <= ceil(n / 2)), the greedy places every letter; the exhaustive cross-check above — brute force versus this heap run on every string up to length 8 — confirms the two conditions always agree.
Complexity: the loop runs once per placement, and each pop and push costs O(log k), where k is the number of distinct letters — at most 26 for lowercase input, so the run is effectively linear. The heap needs O(k) space and the result string needs O(n), which any correct answer must build anyway.