Rearrange string no adjacent duplicates

Given a string s of lowercase letters (1 <= len(s) <= 500), rearrange its characters so that no two ADJACENT characters are the same and return any such arrangement. If it is impossible, return the empty string. For these tests the reference uses a deterministic max-heap tie-broken by lowest character.