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

The accepted answer may produce a correct result, but is likely not the 'correct' answer to this interview brain teaser, nor the most efficient algorithm.

The simple answer is to take the premise of a basic sorting algorithm and alter the looping predicate to check for adjacency rather than magnitude. This ensures that the 'sorting' operation is the only step required, and (like all good sorting algorithms) does the least amount of work possible.

Below is a c# example akin to insertion sort for simplicity (though many sorting algorithm could be similarly adjusted):

string NonAdjacencySort(string stringInput)
{
    var input = stringInput.ToCharArray();

    for(var i = 0; i < input.Length; i++)
    {
        var j = i;

        while(j > 0 && j < input.Length - 1 && 
              (input[j+1] == input[j] || input[j-1] == input[j]))
        {
            var tmp = input[j];
            input[j] = input[j-1];
            input[j-1] = tmp;           
            j--;
        }

        if(input[1] == input[0])
        {
            var tmp = input[0];
            input[0] = input[input.Length-1];
            input[input.Length-1] = tmp;
        }
    }

    return new string(input);
}

The major change to standard insertion sort is that the function has to both look ahead and behind, and therefore needs to wrap around to the last index.

A final point is that this type of algorithm fails gracefully, providing a result with the fewest consecutive characters (grouped at the front).

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.

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