No Twin Neighbours

Write no_twins(text) that rearranges the letters of text so that no two neighbouring letters are the same, and returns the result. Every letter must be used exactly as many times as it appears in text.

Usually many arrangements work, so return the one that comes first in alphabetical (dictionary) order. If no arrangement works, return the empty string ''.

Examples

no_twins('aab')      # returns 'aba'
no_twins('aaab')     # returns ''
no_twins('bbaacc')   # returns 'abacbc'
no_twins('zzyy')     # returns 'yzyz'

In the third example 'abacbc' comes before every other arrangement in dictionary order. An arrangement starting 'abab' would come earlier, but it would leave 'cc' side by side at the end.

Constraints

• 0 <= len(text) <= 50,000
• text holds lowercase letters only

Note

Building every arrangement is out of the question for long strings. Place one letter at a time, always choosing the smallest letter that still lets the rest be arranged.