Reorganize String — Greedy + Heap

Place the busiest, then benchit

Rearrange a string so no two adjacent characters are equal. Greedy insight: always place the character with the highest remaining count. If you don't, a hoarded character piles up and forces a repeat at the end.

A max-heap keyed on count gives that pick. The catch: you can't place the same char twice in a row, so after placing one you hold it aside for exactly one turn (still with its remaining count). Next turn, after picking a different char, you push the held one back. Impossible iff any char's count exceeds ⌈n/2⌉.

// max-heap by remaining count
prev = none
while heap:
  [c, cnt] = heap.pop() # busiest
  result += c; cnt -= 1
  if prev.cnt > 0: heap.push(prev)
  prev = [c, cnt] # hold one turn

Time Complexity

O(N log 26)

N placements, each an O(log 26) heap push/pop. At most 26 distinct characters.

Space Complexity

O(26)

Heap plus the single held char, capped at the alphabet size.

Live Visualization

s = lowercase letters only

Picked (heap top) Held one turn Placed in result In heap

Character heap max-heap by remaining count

On hold (last placed, benched for one turn)

Result so far

picked = – holding = – placed = 0 last char = –

Step 0 / 0

Picked

–

busiest char

On hold

–

benched 1 turn

Placed

of N

Heap size

distinct left

Enter a string and hit Play to watch the greedy reorganizer build a valid result.

✓ Done Speed

Step-by-step trace

#	Action	Picked	Heap (char·count)	Hold	Result

C++ — Reorganize String (LC 767)

string reorganizeString(string s) {
    vector<int> cnt(26, 0);
    for (char c : s) cnt[c - 'a']++;

    // max-heap of {count, char}
    priority_queue<pair<int,char>> pq;
    for (int i = 0; i < 26; ++i)
        if (cnt[i]) pq.push({cnt[i], char('a'+i)});

    string res;
    pair<int,char> prev = {0, '#'};   // held char

    while (!pq.empty()) {
        auto [c, ch] = pq.top(); pq.pop();  // busiest
        res += ch;
        if (prev.first > 0) pq.push(prev);  // release held
        prev = {c - 1, ch};                // hold current for a turn
    }
    return res.size() == s.size() ? res : "";  // "" if impossible
}

📝 My Notes ●

▾

Saved 0 chars