DSA Tracker

Visualize

Reorganize String

Max-heap greedy alternation

time O(n log 26)space O(1)

Treat each (character, count) pair as a node in a max-heap ordered by count. Repeatedly pulling the two most frequent characters left and placing them next to each other guarantees the dominant character never has to sit beside itself, as long as no character starts out more than (n+1)/2 of the string.

Details

Animated on: Rearrange the characters of a string so that no two adjacent characters are the same, or report it is impossible. s = "dcabab".

Problem:Reorganize StringMedium

Max-heap greedy alternation

step 1 / 14

b:2
c:1
d:1
a:2

Count every character in "dcabab": d:1, c:1, a:2, b:2. Max count is 2, and (n+1)/2 = 3, so a valid rearrangement is possible. Laid out in insertion order it is not yet a max-heap.

Pseudocode
1FUNCTION rearrange(s):
2  count <- FREQUENCY of each character in s
3  IF MAX(count) > (LENGTH(s) + 1) / 2:  RETURN ""
4  heap <- BUILD max-heap of (char, count) pairs
5  out <- EMPTY string
6  WHILE SIZE(heap) >= 2:
7    first, second <- EXTRACT-MAX(heap) TWICE
8    APPEND first.char, second.char TO out
9    DECREMENT first.count, second.count
10    IF first.count > 0:  INSERT first INTO heap
11    IF second.count > 0:  INSERT second INTO heap
12  IF SIZE(heap) = 1:  APPEND heap[0].char TO out
13  RETURN out
14END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. Count every character in "dcabab": d:1, c:1, a:2, b:2. Max count is 2, and (n+1)/2 = 3, so a valid rearrangement is possible. Laid out in insertion order it is not yet a max-heap.
  2. Heapify index 1: b:2 outranks c:1 at index 1, so they swap. b:2 keeps sinking from index 3.
  3. Heapify index 0: a:2 outranks d:1 at index 0, so they swap. a:2 keeps sinking from index 2.
  4. Every parent's count is now >= both its children's. The heap is built in O(n) and ready for extraction.
  5. Extract the most frequent remaining character: a:2. 3 nodes left in the heap for now.
  6. Extract the next most frequent, different from a so they can sit adjacent in the output: b:2.
  7. Append 'a' then 'b': out = "ab". Decrement both counts. a:1 and b:1 still remain, so they go back into the heap.
  8. Extract the most frequent remaining character: a:1. 3 nodes left in the heap for now.
  9. Extract the next most frequent, different from a so they can sit adjacent in the output: b:1.
  10. Append 'a' then 'b': out = "abab". Decrement both counts. Both hit zero, so neither is reinserted.
  11. Extract the most frequent remaining character: c:1. 1 node left in the heap for now.
  12. Extract the next most frequent, different from c so they can sit adjacent in the output: d:1.
  13. Append 'c' then 'd': out = "ababcd". Decrement both counts. Both hit zero, so neither is reinserted.
  14. Heap has fewer than 2 nodes left, so the loop ends. Final answer: "ababcd".

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Reorganize String in the editorAll Heap problemsBack to roadmap