拖曳一个字符串,使两个相邻的字母不相同

Question

我一直在努力解决这个面试问题,要求对一个字符串进行洗牌,以便没有两个相邻的字母是相同的.例如,

ABCC - > ACBC

我想到的方法是

1)迭代输入字符串并将(字母,频率)对存储在某个集合中

2)现在通过拉出我们不仅仅拉动的最高频率(即> 0)字母来构建结果字符串

3)每当我们拉信时更新(减少)频率

4)如果所有字母的频率为零,则返回结果字符串

5)如果我们只剩下一个频率大于1的字母,则返回错误

通过这种方法,我们可以为最后一个保存更珍贵(不太频繁)的字母.但为了实现这一点,我们需要一个集合,让我们可以有效地查询密钥,同时有效地按值对其进行排序.喜欢的东西这会工作,除了我们需要保持每个字母检索排序后的集合.

我假设是Unicode字符.

关于使用什么集合的任何想法？还是另一种方法？

Answer 1

您可以按频率对字母进行排序,将排序后的列表分成两半,然后依次从两半中取出字母来构造输出.这需要一个单一的.

例:

如果最高频率的字母数超过字符串长度的一半,则问题无法解决.