Reorganize String

Problem

Rearrange the characters of s so that no two adjacent characters are the same, and return the arrangement, or the empty string if it is impossible.

Use a max-heap of character counts; place the most frequent character, hold it back for one step so it cannot repeat immediately, and return the result only if every character was placed. The arrangement is deterministic for a given input.

Hint

A character is only re-pushed after a different character has been placed.

Test cases

case 1

in: ["aab"]

expected: "aba"

case 2

in: ["aaab"]

expected: ""

case 3

in: ["vvvlo"]

expected: "vlvov"

case 4

in: ["a"]

expected: "a"

case 5

in: [""]

expected: ""

case 6

in: ["aaabbb"]

expected: "ababab"

Starter codePython

def reorganize_string(s):
    # Your code here
    pass

6 test cases · run your code against them in the editor