我一直试图解决这个面试问题，这个问题要求改变一个字符串，这样两个相邻的字母就不一样了 例如，
ABCC - > ACBC
我正在考虑的方法是
1）迭代输入字符串并存储（字母，频率） 配对 一些 采集
2）现在通过拉出我们不仅仅拉动的最高频率（即> 0）字母来构建结果字符串
3）每当我们拉信时更新（减少）频率
4）如果所有字母的频率为零，则返回结果字符串
5）如果我们只剩下一个频率大于1的字母，则返回错误
通过这种方法，我们可以为最后一个保存更珍贵（不太频繁）的字母。但为了实现这一点，我们需要一个集合，它可以让我们有效地查询密钥，同时根据值对其进行有效排序。就像是 这个 除了我们需要在每次检索字母后对集合进行排序时才会有效。
我假设是Unicode字符。
关于使用什么集合的任何想法？还是另一种方法？
您可以按频率对字母进行排序，将排序后的列表分成两半，然后依次从两半中取出字母来构造输出。这需要一个单一的。
例：
ACABBACABAAABBBCCAAAB+BBCCABABACBC如果最高频率的字母数超过字符串长度的一半，则问题无法解决。
为什么不使用两个数据结构：一个用于排序（如堆）和一个用于密钥检索，如字典？
接受的答案可能会产生正确的结果，但可能不是这个采访脑筋急转弯的“正确”答案，也不是最有效的算法。
简单的答案是采用基本排序算法的前提，并改变循环谓词以检查邻接而不是大小。这确保了“排序”操作是唯一需要的步骤，并且（像所有良好的排序算法一样）可以完成最少量的工作。
下面是一个c＃示例，类似于插入排序以简化（虽然可以类似地调整许多排序算法）：
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);
}
标准插入排序的主要变化是函数必须向前看和向后看，因此需要回绕到最后一个索引。
最后一点是这种类型的算法优雅地失败，提供了最少的连续字符（在前面分组）的结果。