Shuffling a string so that no two adjacent letters are the same

Question

I've been trying to solve this interview problem which asks to shuffle a string so that no two adjacent letters are identical For example,

ABCC -> ACBC

The approach I'm thinking of is to

1) Iterate over the input string and store the (letter, frequency) pairs in some collection

2) Now build a result string by pulling the highest frequency (that is > 0) letter that we didn't just pull

3) Update (decrement) the frequency whenever we pull a letter

4) return the result string if all letters have zero frequency

5) return error if we're left with only one letter with frequency greater than 1

With this approach we can save the more precious (less frequent) letters for last. But for this to work, we need a collection that lets us efficiently query a key and at the same time efficiently sort it by values. Something like this would work except we need to keep the collection sorted after every letter retrieval.

I'm assuming Unicode characters.

Any ideas on what collection to use? Or an alternative approach?

Answer 1

You can sort the letters by frequency, split the sorted list in half, and construct the output by taking letters from the two halves in turn. This takes a single sort.

Example:

• Initial string: ACABBACAB
• Sort: AAAABBBCC
• Split: AAAA+BBBCC
• Combine: ABABABCAC

If the number of letters of highest frequency exceeds half the length of the string, the problem has no solution.

Answer 2

Why not use two Data Structures: One for sorting (Like a Heap) and one for key retrieval, like a Dictionary?