using System;

using System.Linq;

using System.Text;

public class Program

{

    public static string ReorganizeString(string s) {

        int count = s.GroupBy(c => c).Max(g => g.Count());

        // One of the item is too frequent, no solutions 

        if (count > (s.Length + 1) / 2)

            return "";

        string st = string.Concat(s

            .GroupBy(c => c)

            .OrderByDescending(g => g.Count())

            .ThenBy(g => g.Key) // not required, just for aesthetic

            .SelectMany(c => c));

        StringBuilder sb = new StringBuilder(s.Length);

        for (int i = 0; i < s.Length / 2; ++i) {

            sb.Append(st[i]);

            sb.Append(st[(st.Length + 1) / 2 + i]);

        }

        // Middle character 

        if (s.Length % 2 != 0)

            sb.Append(st[st.Length / 2]);

        return sb.ToString();

    }

    public static void Main() {

        //TODO: Add more tests

        string[] tests = new string[] {

            "abcd",

            "aabb",

            "aaabb",

            "aaabc",

            "a",

            "aa",

            "ab"

        };

        string result = string.Join(Environment.NewLine, tests

            .Select(test => $"{test,10} => {ReorganizeString(test)}"));

        Console.Write(result);

    }

}