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

问题描述：

给定一个字符串作为字母数字字符，其中某些字符在连续的地方重复，我们必须分散重复的字符以使它们不连续。打印所有可能的字符串，不包含重复字符中相邻的相等字符字符串

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}

当最高频率的字符计数将是超过总字数的一半，则不会生成输出。

现在我不能够使用地图

你做了什么/你是如何解决这个问题的？ – depperm

答

可以散射当且仅当没有字符发生比天花板倍（串/ 2长度）更打印所有所需的输出。你能看出为什么分散一个角色是不可能的？（请回答以下。）

我们可以适合通过交替装配它们而获得的字符的最大数量，即“ABABABA”给出了字母的实例的最大数目“一“可以容纳7个字符，4个;这个数字可以使用公式天花板（字符串长度/ 2）计算出来。

现在，算法如下：由他们经常出现在字符串中（所以“abcdabcaba”将成为“aaaabbbccd”），然后使用反向rail fence cipher with 2 rails字符排序;也就是说，将已排序的字符串拆分成一半（如果它的长度是偶数，则将其拆分为一半;如果不是，则拆分它使得前半部分还有一个字符），然后建立最终的字符串，交替进行每个字符串中的字符，从第一个开始。因此，“aaaabbbccd”将成为“ababacacbd”。我会留给你证明这是有效的。

要做到这一点，你不妨考虑反向栅栏下会发生什么不同大小的字符块。

类=“搅局”>

类=“扰流”>

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

相关推荐