DIY: Reorganizing a String

Problem statement

In this challenge, you will be given a string as input. Your task is to check whether the letters in this string can be reorganized such that the adjacent letters are not identical. If the reorganization of letters is possible, output any possible result. Otherwise, return an empty string.

Input

The function’s input will be a string called str. The following is an example input.

str = "abaacdda"

Output

The function’s output will also be a string that is a reorganization of the input string. For the above-mentioned input, one possible output is:

"abacadad"

Note: If a valid reorganization of the string is not possible, return an empty string.