Medium

题目描述

给定一个字符串 s，重新排列字符串中的字符，使得任意两个相邻的字符都不相同。

返回 s 的任意可能的重新排列。若不可能，则返回 ""。

示例 1：

输入：s = "aab"
输出："aba"

示例 2：

输入：s = "aaab"
输出：""

提示：

  • 1 <= s.length <= 500
  • s 由小写英文字母组成

提示：

  • 交替放置最常见的字母。

解题思路

这道题需要重新排列字符串，使得相邻字符不同。核心思路是贪心策略：每次选择剩余字符中出现次数最多的字符来填充。

解题思路：

  1. 可行性判断：对于长度为 n 的字符串，如果某个字符出现次数超过 (n+1)/2，则无法满足相邻不同的要求。

  2. 优先级队列解法（推荐）：

    • 统计每个字符的出现次数
    • 使用最大堆（优先级队列）按出现次数排序
    • 每次取出出现次数最多的字符放入结果
    • 为避免相邻重复，使用临时变量存储上一个字符，下轮再放回堆中

  3. 奇偶位置填充解法：

    • 先将出现次数最多的字符放在偶数位置（0,2,4…）
    • 再依次将其他字符放在剩余位置
    • 这种方法更直观，但实现稍复杂

两种解法时间复杂度相同，优先级队列解法代码更简洁清晰。

代码实现

class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> count;
        for (char c : s) {
            count[c]++;
        }
        
        // 检查是否可能重构
        int maxCount = 0;
        for (auto& p : count) {
            maxCount = max(maxCount, p.second);
        }
        if (maxCount > (s.length() + 1) / 2) {
            return "";
        }
        
        // 使用优先级队列
        priority_queue<pair<int, char>> pq;
        for (auto& p : count) {
            pq.push({p.second, p.first});
        }
        
        string result = "";
        pair<int, char> prev = {0, '#'};
        
        while (!pq.empty()) {
            auto curr = pq.top();
            pq.pop();
            
            result += curr.second;
            curr.first--;
            
            if (prev.first > 0) {
                pq.push(prev);
            }
            
            prev = curr;
        }
        
        return result.length() == s.length() ? result : "";
    }
};

class Solution:
    def reorganizeString(self, s: str) -> str:
        from collections import Counter
        import heapq
        
        count = Counter(s)
        
        # 检查是否可能重构
        max_count = max(count.values())
        if max_count > (len(s) + 1) // 2:
            return ""
        
        # 使用最大堆（Python是最小堆，所以用负数）
        heap = [(-freq, char) for char, freq in count.items()]
        heapq.heapify(heap)
        
        result = []
        prev = None
        
        while heap:
            # 取出频次最高的字符
            freq, char = heapq.heappop(heap)
            result.append(char)
            
            # 如果前一个字符还有剩余，放回堆中
            if prev and prev[0] < 0:
                heapq.heappush(heap, prev)
            
            # 更新当前字符的频次作为下一轮的prev
            prev = (freq + 1, char)
        
        return ''.join(result) if len(result) == len(s) else ""

public class Solution {
    public string ReorganizeString(string s) {
        var count = new Dictionary<char, int>();
        foreach (char c in s) {
            count[c] = count.GetValueOrDefault(c, 0) + 1;
        }
        
        // 检查是否可能重构
        int maxCount = count.Values.Max();
        if (maxCount > (s.Length + 1) / 2) {
            return "";
        }
        
        // 使用优先级队列（最大堆）
        var pq = new PriorityQueue<(int freq, char c), int>();
        foreach (var kvp in count) {
            pq.Enqueue((kvp.Value, kvp.Key), -kvp.Value); // 负数实现最大堆
        }
        
        var result = new StringBuilder();
        (int freq, char c) prev = (0, '#');
        
        while (pq.Count > 0) {
            var curr = pq.Dequeue();
            result.Append(curr.c);
            curr.freq--;
            
            if (prev.freq > 0) {
                pq.Enqueue(prev, -prev.freq);
            }
            
            prev = curr;
        }
        
        return result.Length == s.Length ? result.ToString() : "";
    }
}

var reorganizeString = function(s) {
    const freq = {};
    for (let char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    
    const maxHeap = Object.keys(freq).sort((a, b) => freq[b] - freq[a]);
    
    if (freq[maxHeap[0]] > Math.ceil(s.length / 2)) {
        return "";
    }
    
    const result = new Array(s.length);
    let index = 0;
    
    for (let char of maxHeap) {
        let count = freq[char];
        while (count > 0) {
            result[index] = char;
            index += 2;
            if (index >= s.length) {
                index = 1;
            }
            count--;
        }
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值说明
时间复杂度O(n log k)n为字符串长度，k为不同字符数量。每次堆操作需要O(log k)时间，总共n次操作
空间复杂度O(k)需要存储字符计数的哈希表和优先级队列，k为不同字符数量，最多26个小写字母

相关题目