本文共 1859 字，大约阅读时间需要 6 分钟。

解决方案：判断是否能重新排布字符串中的字母，使得相邻字符不同。可用大根堆贪心算法构造结果。

步骤解释：

代码实现：使用Python的heapq模块，大根堆通过负数实现。

重新排布字符串中的字符

步骤解释：

代码实现：

import collections
import heapq
class Solution:
    def reorganizeString(self, S: str) -> str:
        if len(S) < 2:
            return S
        
        # 统计字符频率
        char_count = collections.defaultdict(int)
        for c in S:
            char_count[c] += 1
        
        # 确定最大频率
        max_freq = max(char_count.values())
        if max_freq > (len(S) + 1) // 2:
            return ""
        
        # 初始化大根堆，存储负数频率和字符
        heap = [(-freq, char) for char, freq in char_count.items()]
        heapq.heapify(heap)
        
        result = []
        
        while len(heap) > 1:
            # 取出两个字符
            freq1, char1 = heapq.heappop(heap)
            freq2, char2 = heapq.heappop(heap)
            
            # 增加结果
            result.append(char1)
            result.append(char2)
            
            # 减少频率
            char_count[char1] -= 1
            char_count[char2] -= 1
            
            # 如果频率仍有剩余，重新入堆
            if char_count[char1] > 0:
                heapq.heappush(heap, (-char_count[char1], char1))
            if char_count[char2] > 0:
                heapq.heappush(heap, (-char_count[char2], char2))
        
        # 处理剩下的字符（奇数长度的情况）
        if heap:
            result.append(heap[0][1])
        
        return ''.join(result)

代码解释：

• 统计字符频率： 使用collections.defaultdict遍历字符串，记录每个字符的出现次数。
• 检查可行性： 计算最大频率，如果超过允许值，返回空字符串。
• 初始化堆： 将频率和字符转换为元组，使用负数构建大根堆，以便使用贪心算法。
• 构造结果字符串： 每次从堆中取出两个字符，减少它们的频率，若频率仍有剩余，再次入堆。
• 处理奇数长度： 当堆中剩下一个字符时，添加到结果中。

通过这种方法，可以高效地判断字符串是否可以重新排列并构造结果。