How to efficiently rearrange characters in a string so that there are no pairs? [duplicate]

Question

There is a string of up to 10^5 A..Z characters. The task is to rearrange it so that none of the characters forms a row. For multiple solutions the one that comes first alphabetically is correct. And it has to be done in reasonable time, of course.

So I tried two approaches and one of them rearranges correctly but very inefficiently, and the other one has broken logic, I guess.

Slow approach.

1. Sort the array of chars
2. Rearrange in place, similar to the insertion sort (that's why it is so slow)

Incorrect approach (doesn't always give the alphabetically first answer)

1. Sort
2. Move the elements starting from the end to another array, maintaining the invariant
3. Reverse

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

Examples:

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

---

Here is the model solution algorithm in details. I think I am not allowed to post the actual code, so it's like this:

1. Build the histogram. It can be stored in an array of int, indexes being the ascii-codes, so no mapping is needed.
2. Build the new string:
   • for each character go alphabetically, from A to Z
   • if there is no such symbol according to the histogram, move to the next
   • if the previous written symbol was the same, move to the next (if it is not the first iteration)
   • write the first found suitable character
   • decrease the number in the histogram
   • if there's (length-i+2)/2 of the current symbol (half of what's left), break from this cycle and go to the next symbol in the string.

It is much shorter and simpler than the mess I wrote eventually (although it worked fine, and thank you very much for the help).

Answer 1

Good point Paul R. If you have your histogram with the number of occurrences of each element, you could then sort those buckets by number of occurrences from high to low. As long as the number of occurrences in one bucket is not greater than the number of buckets, you should be able to form a viable string. Starting with the largest buckets, loop through each occurrence in the next largest bucket down to the smaller buckets.

For example, AAAAABBCRRSTT

AAAAA BB C RR S TT -> AAAAA BB RR TT C S

ABARATACASBRT