打印所有可能的字符串，不包含重複字符中相鄰的相等字符字符串

Question

給定一個字符串作爲字母數字字符，其中某些字符在連續的地方重複，我們必須分散重複的字符以使它們不連續。

input: aaaabbbcdd11 
Output: abababacd1d1 or any other valid combination. 

如果沒有這樣的組合，那麼應該沒有輸出。

這個問題在面試中被問到。我仍然無法解決這個算法。我不確定這是否是正確的論壇。但我非常好奇知道可以用來解決這個問題的正確的算法/數據結構。

我試圖創建一個哈希（地圖），以便我可以保持所有字符的計數。

str = "aaaabbbcdd11" 
hashChrs = {} 
for item in list(str): 
    if item in hashChrs: 
     hashChrs[item] = hashChrs[item] + 1 
    else: 
     hashChrs[item] = 1 
print hashChrs 

{ '一個'：4， '1'：2， 'C'：1， 'B'：3， 'd'：2}

當最高頻率的字符計數將是超過總字數的一半，則不會生成輸出。

現在我不能夠使用地圖

Answer 1

可以散射當且僅當沒有字符發生比天花板倍（串/ 2長度）更打印所有所需的輸出。你能看出爲什麼分散一個角色是不可能的？ （請回答以下。）

我們可以適合通過交替裝配它們而獲得的字符的最大數量，即「ABABABA」給出了字母的實例的最大數目「一「可以容納7個字符，4個;這個數字可以使用公式天花板（字符串長度/ 2）計算出來。

現在，算法如下：由他們經常出現在字符串中（所以「abcdabcaba」將成爲「aaaabbbccd」），然後使用反向rail fence cipher with 2 rails字符排序;也就是說，將已排序的字符串拆分成一半（如果它的長度是偶數，則將其拆分爲一半;如果不是，則拆分它使得前半部分還有一個字符），然後建立最終的字符串，交替進行每個字符串中的字符，從第一個開始。因此，「aaaabbbccd」將成爲「ababacacbd」。我會留給你證明這是有效的。

要做到這一點，你不妨考慮反向柵欄下會發生什麼不同大小的字符塊。