All problems

Tidy Tile Row

Medium · greedy

A sign painter has a box of letter tiles, given as the string tiles (lowercase letters, repeats allowed). She wants to line all the tiles up in a single row so that no two neighbouring tiles show the same letter.

Among all the rows that follow that rule, she likes the one that comes first in alphabetical order. Two rows of the same length are compared letter by letter from the left, and the row with the earlier letter at the first position where they differ comes first.

Return that row as a string. If no row satisfies the rule, return an empty string.

Examples

Example 1

Input: tiles = "aabb"

Output: "abab"

The only valid rows are abab and baba, and abab comes first.

Example 2

Input: tiles = "cbaaa"

Output: "abaca"

The three a's have to take the first, third and fifth places. Putting b before c in the gaps gives the earliest row.

Example 3

Input: tiles = "aaab"

Output: ""

Three a's cannot be kept apart by a single b.

Constraints