Warning: This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#767) before relying on it.

Reorganize String

An interactive visualization of the greedy max-heap approach to Reorganize String. Watch how character frequencies drive a priority queue to build a string with no two adjacent characters the same.

Heap / Priority Queue LeetCode 767 ↗ Medium

The Problem

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Interactive Visualization

Input String

Preset

Speed:

Input String

Character Frequencies

Max-Heap (neg. freq, char)

Heap will appear after counting frequencies

Previous Character (On Hold)

No character on hold

Result String

Result will be built character by character

Step Log

Press Step or Play to begin.

Code

import java.util.PriorityQueuefun reorganizeString(s: String): String {    val count = mutableMapOf<Char, Int>()    for (ch in s) count[ch] = (count[ch] ?: 0) + 1    val heap = PriorityQueue<Pair<Int,Char>>(compareBy { it.first })    for ((ch, freq) in count) heap.add(-freq to ch)    val result = mutableListOf<Char>()    var prevFreq = 0; var prevCh = ' '    while (heap.isNotEmpty()) {        val (freq, ch) = heap.poll()        result.add(ch)        if (prevFreq < 0)            heap.add(prevFreq to prevCh)        prevFreq = freq + 1; prevCh = ch    }    val res = result.joinToString("")    return if (res.length == s.length) res else ""

import heapqfrom collections import Counterdef reorganizeString(s):    count = Counter(s)    heap = [(-freq, ch) for ch, freq in count.items()]    heapq.heapify(heap)    result = []    prev_freq, prev_ch = 0, ''    while heap:        freq, ch = heapq.heappop(heap)        result.append(ch)        if prev_freq < 0:            heapq.heappush(heap, (prev_freq, prev_ch))        prev_freq, prev_ch = freq + 1, ch    result = ''.join(result)    return result if len(result) == len(s) else ""

How It Works

Key Insight

The greedy strategy is to always place the most frequent remaining character that is different from the one just placed. A max-heap (priority queue) ordered by frequency makes this selection efficient. By holding back the previously placed character for one round, we guarantee no two adjacent characters are the same.

The Algorithm

Count frequencies: Use Counter(s) to tally each character.
Build a max-heap: Push (-freq, char) pairs (negative because Python's heapq is a min-heap).
Iterate: Pop the top of the heap (most frequent char), append it to the result.
Hold back: Before pushing back, save the current character as "previous." On the next iteration, if the previous character still has remaining frequency, push it back into the heap.
Validate: If the result length equals the input length, the rearrangement succeeded. Otherwise, it is impossible (return "").

Why It Works

By always picking the highest-frequency character that is not the same as the last one placed, we distribute characters as evenly as possible. The "on hold" mechanism prevents the same character from being placed twice in a row. If at any point the heap is empty but we still have a character on hold with remaining frequency, the algorithm terminates early — meaning the most frequent character appears more than (n + 1) / 2 times, making rearrangement impossible.

Complexity

Time O(n log A)

Space O(A)

Where n is the length of the string and A is the alphabet size (at most 26). Each of the n iterations involves a heap pop and possibly a push, each O(log A). The heap and frequency map store at most A entries.