Readme

767.Reorganize-String

本题本质上1953.Maximum-Number-of-Weeks-for-Which-You-Can-Work的follow up，要求将具体的规划方案打印出来。此题和1054.Distant-Barcodes一模一样。类似地，本题还是358. Rearrange String k Distance Apart在k=2时的特例。

解法1：贪心

我们将所有的字符按照频次重新排序，例如abcbba，就会重排成bbbaac。对于频次较高的字符我们会尽量安排它们间隔排列，即先放在奇数的位置上。一旦奇数位置上放满了，就从头开始在偶数位置上。这样就最大限度地避免高频词的字符被放在相邻的位置。

从上面的贪心策略我们可以推论出，只要最高频次的字符的数目不多于总数目的一半，那么用上面的方法构造出的结果就是合法的。反之必然会有相邻的字符相同。

解法2：优先队列

之前的方法是跳跃地构造结果。用优先队列可以直接顺序地构造结果。

基本的思想就是：每个回合尽量使用当前频次最多的两个字母。如果不优先使用频次最多的字母，则越有可能提早耗尽其他频次较低的字符种类。当最终手头只剩一种字母时，构造就无法进行下去。

数据结构上，维护一个优先队列来实时得到当前频次最多的两个字母。只要每次能取两个不同字母组成一对加入字符串，可以保证顺利构造结果。记得使用完之后，将这两种字母频次减一之后再放入队列之中。

失败的条件：队列中只有一种字母，并且字母的频次大于等于2.