难度: Medium
给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。
返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。
示例 1:
输入: s = "aab" 输出: "aba"
示例 2:
输入: s = "aaab" 输出: ""
提示:
1 <= s.length <= 500s只包含小写字母
Submission
运行时间: 20 ms
内存: 0.0 MB
class Solution:
def reorganizeString(self, S: str) -> str:
N = len(S)
A = []
for c, x in sorted((S.count(x), x) for x in set(S)):
if c > (N+1)/2: return ""
A.extend(c * x)
ans = [None] * N
#print(A[:N//2])
ans[::2], ans[1::2] = A[N//2:], A[:N//2]
return "".join(ans)
Explain
该题解的思路是先统计每个字母出现的次数，然后按照出现次数从大到小排序。如果出现次数最多的字母超过了 (N+1)/2，则无法构造出满足条件的字符串，返回空字符串。否则，将字母按照出现次数拼接成一个列表 A。接下来，将列表 A 均分成两部分，前一半放在答案字符串的偶数下标位置，后一半放在奇数下标位置，这样就能保证相邻字母不同。最后将答案数组拼接成字符串返回。
时间复杂度: O(NlogN)
空间复杂度: O(N)
class Solution:
def reorganizeString(self, S: str) -> str:
N = len(S)
A = []
# 统计每个字母出现的次数，并按照次数从大到小排序
for c, x in sorted((S.count(x), x) for x in set(S)):
# 如果出现次数最多的字母超过了 (N+1)/2，无法构造满足条件的字符串
if c > (N+1)/2: return ""
# 将字母按照出现次数拼接成列表 A
A.extend(c * x)
ans = [None] * N
# 将列表 A 均分成两部分，前一半放在偶数下标，后一半放在奇数下标
ans[::2], ans[1::2] = A[N//2:], A[:N//2]
# 将答案数组拼接成字符串返回
return "".join(ans)
Explore
这是因为如果某个字符的出现次数超过了(N+1)/2，那么无论如何排列这些字符，至少会有两个相邻位置被同一个字符占据。例如，假设字符'a'出现了比(N+1)/2更多的次数，即使将'a'分布在尽可能分散的位置，由于'a'的数量超过了字符串总长度的一半，还是会存在至少两个'a'相邻的情况。因此，当任何字符的出现次数超过(N+1)/2时，不可能重构字符串使得相邻的字符都不相同，所以返回空字符串。
将字符列表A按出现次数从大到小排序后均分到偶数和奇数位置的方法基于字符的频率分布。首先将频率最高的字符放在偶数位置，接着填充奇数位置，然后再次从偶数位置开始填充剩余字符。这样做的目的是尽可能地分散高频字符，避免相邻。由于之前已确保没有字符的频率超过了(N+1)/2，所以通过这种方式可以最大程度上避免任何两个相邻位置被相同字符占据。
使用S.count(x)在列表推导式中对每个字符进行计数虽然简单直观，但其效率并不高，因为每次调用count方法都会重新遍历整个字符串S，导致总的时间复杂度接近O(n^2)，其中n是字符串的长度。一个更高效的方法是使用Python的collections.Counter类，这可以在O(n)时间内完成对所有字符的计数，显著提高效率。
虽然使用sorted函数可以有效地对字符按出现次数进行排序，但这涉及到对整个列表的全排序，其时间复杂度是O(n log n)。使用堆（优先队列）可以在一些情况下进行优化，尤其是当我们只关心最频繁出现的几个元素时。例如，可以使用最大堆来维护出现次数最多的字符，这对于动态或增量地处理数据时更加高效。但在当前的应用场景中，由于字符种类有限（最多256个ASCII字符），使用sorted函数对这么小的数据集进行排序的性能损耗并不大。