LeetCode第765题Reorganize String简要分析

LeetCode 第765题 Reorganize String

题目：

Given a string , check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = “aab”

Output: “aba”

Example 2:

Input: S = “aaab”

Output: “”

Note:

will consist of lowercase letters and have length in range .

分析:

最终结果中任何相邻的两个字符不能相同，意味着给定字符串中重复次数最多的字符每隔一个空位排列后，即的长度不能超过的长度，否则必定有两个相邻，则返回空字符串。

因此我们需首先统计各个字符出现次数并按升序排列，生成新的列表。在此过程中，如果任何字符的总出现次数超过了上面所说的限制，意味着该字符串无法按照要求重新排列，则立刻返回空字符串。

然后建立与给定字符串相同长度的空列表。

接下来，按照出现频率从高到低，每间隔一位将字符插入到空列表中，即按照位置序号填充，直至列表末尾。然后再从头开始填充另一半空位。这样任何相邻的字符都不相同，符合题目要求。

最后，把生成的新列表转化为字符串作为最终结果返回。

例子1:

输入为。经统计后出现2次，出现1次，则生成的统计列表为，并建立空列表。然后开始填充，长度为3，则一半取整为1。首先填充后一半，即出现频次高的字符，也就是。每间隔一位填入空列表，得到。接下来填充剩下的一半，即，得到。最后把列表转换为字符串返回即为最终结果。

例子2:

输入为。经统计后出现3次，出现1次，则生成的统计列表为。字符串总长度为4，出现次数最多的为，3 * 2 - 1 > 4，不满足长度限制。至少需要长度为5的字符串才能确保所有均不相邻。因此该输入无解，返回空字符串。

完整Python代码：

参考资料：

LeetCode Problem 765 solution