How to efficiently reorder characters in a string so that there are no pairs?

There is a string of up to 10 ^ 5 characters A..Z. The challenge is to rearrange it so that none of the characters form a string. For multiple solutions, the correct one is the one that comes first in alphabetical order. Of course, this must be done within a reasonable time frame.

So, I tried two approaches, and one rebuilds correctly, but very inefficiently, and the other apparently broke the logic.

Slow approach.

• Sorting an array of characters
• Rearrange in place, similar to insertion sort (why is it so slow)

Wrong approach (does not always give the first answer in alphabetical order)

• Sorting
• Move elements, starting from the end, to another array, keeping the invariant
• Reverse

I'm really stuck and can't think of anything else.

Examples:

"HHABC" -> "ABHCH";
"CBAXXXX" -> "XAXBXCX";
"AAABBBCCCCCCCDDDDD" -> "ABABACBCDCDCDCDCDC";

      

        
        
        
      

    

Here is a detailed algorithm for solving the model. I think I am not allowed to post the actual code, so like this:

• Plot a histogram. It can be stored in an int array, the indices are ascii codes, so no matching is required.
• Create a new line:
  • for each character goes in alphabetical order, from A to Z
  • if, according to the histogram, there is no such symbol, go to the next
  • If the previous recorded character was the same, move on to the next one (unless it is the first iteration)
  • write the first matching character found
  • decrease the number on the histogram
  • if there is (length-i + 2) / 2 of the current character (half of what is left), break away from that loop and go to the next character in the line.

It's much shorter and easier than the mess I ended up writing (although it worked great and thanks a lot for the help).