题目
解答 & 代码
- 解法一：贪心 + 大根堆（按序填充）
- 解法二：贪心 + 数组排序（间隔填充）

题目

给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。
返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

示例：

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

1
2
输入: s = "aaab"
输出: ""

解答 & 代码

解法一：贪心 + 大根堆（按序填充）

按顺序填充结果字符串的每一位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct cmp {
    bool operator()(pair<char, int> pair1, pair<char, int> pair2) {
        return pair1.second < pair2.second;
    }
};

class Solution {
public:
    string reorganizeString(string s) {
        int len = s.size();
        // 1. 统计每个字符出现的次数
        unordered_map<char, int> chCntMap;
        for(int i = 0; i < len; ++i)
        {
            ++chCntMap[s[i]];
            // 如果某个字符出现次数 > (len + 1) / 2，则无法重构，直接返回 ""
            if(chCntMap[s[i]] > (len + 1) / 2)
                return "";
        }

        // 2. 将 <字符，出现次数> 存入大根堆（优先队列实现）
        priority_queue<pair<char, int>, vector<pair<char, int>>, cmp> maxHeap;
        for(auto it = chCntMap.begin(); it != chCntMap.end(); ++it)
            maxHeap.push(make_pair(it->first, it->second));
        // 3. 重构字符串：每次选择剩余次数最大（且不和上一位重复）的字符插入结果字符串尾部
        // 为了避免和上一位重复，每次插入后从大根堆中暂时弹出本次插入的字符 pair，
        // 等下一轮过后再重新插回到大根堆
        string result;
        pair<char, int> tempPair(' ', 0);
        while(maxHeap.size() != 0)
        {
            pair<char, int> maxPair = maxHeap.top();    // 选择剩余次数最大的字符
            result.push_back(maxPair.first);            // 插入结果字符串尾部
            maxHeap.pop();                                // 从大根堆中暂时弹出该字符 pair
            --maxPair.second;                            // 剩余次数 -1

            // 若 tempPair 的剩余次数大于 0，则重新插入到大根堆
            if(tempPair.second != 0)
                maxHeap.push(tempPair);
            tempPair = maxPair;                    // 将本次插入的字符 pair 记作新的 tempPair
        }
        return result.size() == len ? result : "";
    }
};

复杂度分析：设字符串 s 长为 n，包含不同字符种数 [中等] 767. 重构字符串 - 图1

时间复杂度：操作 n 次大根堆，每次插入/删除时间复杂度
空间复杂度：

执行结果：

1
2
3
4
执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 27.67% 的用户
内存消耗：6 MB, 在所有 C++ 提交中击败了 90.73% 的用户

解法二：贪心 + 数组排序（间隔填充）

先填充结果字符串的偶数位 0, 2, 4, ...，再填充字符串的奇数位 1, 3, 5, ...

对字符及出现次数计数
将 <字符，出现次数> pair 存入数组 arr，并降序排序
遍历数组 arr，

设当前遍历到的字符为 ch，出现次数为 cnt

将 ch 按偶数位插入结果字符串，如果偶数位已经插完，则按奇数位插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
private:
  static bool cmp(pair<char, int> pair1, pair<char, int> pair2)
  {
      return pair1.second > pair2.second;
  }
public:
  string reorganizeString(string s) {
      int len = s.size();
      // 1. 统计字符及其出现次数
      unordered_map<char, int> chCntMap;
      for(int i = 0; i < len; ++i)
      {
          ++chCntMap[s[i]];
          // 如果某个字符出现次数 > (len + 1) / 2，则无法重构，直接返回 ""
          if(chCntMap[s[i]] > (len + 1) / 2)
              return "";
      }

      // 2. 将 <字符，出现次数> pair 存入数组 arr，并降序排序
      vector<pair<char, int>> arr;
      for(auto it = chCntMap.begin(); it != chCntMap.end(); ++it)
          arr.push_back(make_pair(it->first, it->second));
      sort(arr.begin(), arr.end(), cmp);

      // 3. 填充结果字符串的偶数位 0, 2, 4, ...，再填充字符串的奇数位 1, 3, 5, ...
      string result(len, ' ');
      int idx = 0;
      for(int i = 0; i < arr.size(); ++i)        // 遍历数组 arr
      {
          char ch = arr[i].first;                // 选择剩余的出现次数最多的字符
          int cnt = arr[i].second;
          for(int j = 0; j < cnt; ++j)
          {
              result[idx] = ch;
              idx += 2;                        // 间隔填充到结果字符串（先填充偶数位，填完偶数位再填奇数位）
              if(idx >= len)                    // 如果已填完结果字符串的偶数位，则开始填充奇数位
                  idx = 1;
          }
      }
      return result;
  }
};

复杂度分析：设字符串 s 长为 n，包含不同字符种数 [中等] 767. 重构字符串 - 图5

时间复杂度：数组排序
空间复杂度：

执行结果：

1
2
3
4
执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 27.67% 的用户
内存消耗：6.1 MB, 在所有 C++ 提交中击败了 45.13% 的用户