Pattern visualizer

Rearrange Characters

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. Animated on: Rearrange the characters of a string so that no two adjacent characters are the same, or report it is impossible. s = "dcabab"..

Max-heap greedy alternation

time O(n log 26)space O(1)step 1 / 14

b:2

c:1

d:1

a:2

line 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

Where to practice Heap

Practice Heap problems All Heap problems Back to roadmap