← DSA Atlas
Dedicated problem page · #767

Reorganize String

MediumHeap and Priority QueueGreedy most-frequent-first placementMax-heap on character counts
Solve on LeetCode ↗
767
MediumHeap and Priority QueueMax-heap on character countsGreedy most-frequent-first placement

Reorganize String

Given a string s, rearrange its characters so that no two adjacent characters are the same. Return any valid rearrangement, or an empty string if it is impossible.

Open official problem prompt ↗
In plain English

Produce an ordering of the characters where equal characters never touch, or prove none exists.

Picture it like this

Seating guests who dislike their duplicates side by side: always seat the largest remaining group first, but never let a group take two seats in a row — make it wait one seat before it can be seated again.

Example
Input
s = "aab"
Output
"aba"
Why
The two a's are separated by the single b, so no two adjacent characters match.
Constraints
1 <= s.length <= 500s consists of lowercase English letters
Pattern lesson

See the pattern, then code

Greedy most-frequent-first placement
Recognition clue

You must space identical items apart and always want to place the item you have the most of first. Repeatedly pulling the current maximum count is the signature of a max-heap greedy.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. The character with the highest remaining count is the most constrained, so place it first each step. Hold the just-placed character aside for exactly one turn so it cannot land in the very next position, then return it to the heap.

New words, made simpleKnow these before the algorithm
Max-heap
A heap that yields the largest key first; in Python simulated by pushing negated counts into a min-heap.
Greedy placement
Committing to the locally best choice (most frequent character) at each step.
Cooldown / hold
Withholding the just-used character for one turn so it cannot be placed adjacently.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try all permutations / backtracking

Exponential and hopeless for n up to 500.

Generate arrangements and check the adjacency rule.

Time O(n! * n)Space O(n)
Best choiceMax-heap greedy with one-step hold

Linear-ish and provably optimal for this adjacency constraint.

Always append the most frequent remaining character, holding the previous one for exactly one placement.

Time O(n log k)Space O(k)
The rule we keep true

Invariant

The last character written to the result is never immediately available in the heap for the next pick, so consecutive positions always hold different characters.

Why this is correct

Reasoning

Placing the highest-count character first uses up the scarcest 'space' first. A valid arrangement exists exactly when no character exceeds (n+1)/2 occurrences; the hold-one-turn rule guarantees that if such a character existed it would eventually be forced adjacent, leaving the heap empty while characters remain — detected by the final length check.

The algorithm in three movesSay these aloud before coding
1Count characters and build a max-heap keyed by count

heap = [(-2,'a'),(-1,'b')]

2Pop the most frequent character and append it to the result

place 'a' -> res='a', hold ('a',1)

3Keep the previous character on hold and only re-insert it once one more character has been placed

place 'b' -> re-add 'a' -> place 'a' -> 'aba'

4If the built string is shorter than s, no valid arrangement exists — return ""

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
a:20
b:11
1 · Reads="aab"
2 · AskHow many of each?
3 · Update stateheap = [(-2,'a'),(-1,'b')]
4 · Result'a' is most frequent
Key takeaway

Counts as a max-heap; the most frequent character 'a' is placed first, then held one turn.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-8Counts to max-heap

    Negate counts so Python's min-heap surfaces the most frequent character first.

  2. 2
    Lines 12-14Place the max

    Pop the top character and append it to the result string being built.

  3. 3
    Lines 15-17Delayed re-insertion

    Push back the previously placed character (if it still has count) only now, after one more placement, enforcing the one-gap rule.

  4. 4
    Lines 19-20Feasibility check

    If the result is shorter than s, some character was too frequent to separate — return the empty string.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • single character string like "a" (already valid)
  • a character that appears more than (n+1)/2 times, e.g. "aaab" -> ""
  • all identical characters
  • even split like "aabb"
!

Common beginner mistakes

  • Re-inserting the held character immediately, which lets it sit adjacent to itself
  • Forgetting to drop the held character once its count hits zero (guarded by prev[0] < 0)
  • Not checking the impossibility case via the final length comparison
  • Comparing counts by character value rather than by frequency
Check your understanding

Exactly when is a valid reorganization impossible?

More in Heap and Priority Queue

#215Kth Largest Element in an ArrayBounded min-heap of size k#295Find Median from Data StreamTwo balanced heaps#373Find K Pairs with Smallest Sumsk-way merge with a heap#502IPOGreedy with a max-heap of affordable options#621Task SchedulerFill idle slots around the most frequent task#692Top K Frequent WordsCount then heap-order by frequency and word