重构字符串 图解题解

这道题到底在问什么

输入

s="aab"

输出

"aba" （a 隔开放，b 夹中间）

输入

s="aaab"

输出

"" （a 有 3 个，太多，挤不开）

最优解：一步一步想明白

1. 3记住「先判 max ≤ ⌊(n+1)/2⌋，再按频次降序先填偶位后填奇位」，下面每帧都在套它。limit = ⌊(6+1)/2⌋ = 3。
2. 4第一步先数清每个字符各出现几次，结果记在右边的频次表里。
3. 5扫到第 0 个字符 'a'，它的计数变成 1。右边频次表实时更新。
4. 6扫到第 1 个字符 'a'，它的计数变成 2。右边频次表实时更新。
5. 7扫到第 2 个字符 'a'，它的计数变成 3。右边频次表实时更新。
6. 8扫到第 3 个字符 'b'，它的计数变成 1。右边频次表实时更新。
7. 9扫到第 4 个字符 'b'，它的计数变成 2。右边频次表实时更新。
8. 10扫到第 5 个字符 'c'，它的计数变成 1。右边频次表实时更新。
9. 11数完后看最多的 'a'（3 个）和 limit=3 比：3 ≤ 3，说明排得开，继续填。
10. 12下面这条 6 格的带子就是答案的槽位（'·' 表示空）。按频次从多到少：'a' → 'b' → 'c'，先往偶数位塞。
11. 13轮到 'a'，按当前 idx 把它放到下标 0（紫色框）。
12. 14'a' 落在下标 0（绿色），idx 每次 +2 跳着走，保证同一个字符之间至少隔一格。
13. 15轮到 'a'，按当前 idx 把它放到下标 2（紫色框）。
14. 16'a' 落在下标 2（绿色），idx 每次 +2 跳着走，保证同一个字符之间至少隔一格。
15. 17轮到 'a'，按当前 idx 把它放到下标 4（紫色框）。
16. 18'a' 落在下标 4（绿色），idx 每次 +2 跳着走，保证同一个字符之间至少隔一格。
17. 19偶数位 0,2,4 都填满了，下标超出末尾，于是跳回下标 1 开始填奇数位。紫色框就是 'b' 要落的新位置。
18. 20'b' 落在下标 1（绿色），idx 每次 +2 跳着走，保证同一个字符之间至少隔一格。
19. 21轮到 'b'，按当前 idx 把它放到下标 3（紫色框）。
20. 22'b' 落在下标 3（绿色），idx 每次 +2 跳着走，保证同一个字符之间至少隔一格。
21. 23轮到 'c'，按当前 idx 把它放到下标 5（紫色框）。
22. 24'c' 落在下标 5（绿色），idx 每次 +2 跳着走，保证同一个字符之间至少隔一格。
23. 25全部填完，得到 "ababac"。从头检查相邻：'a'≠'b'，'b'≠'a'，'a'≠'b'，'b'≠'a'，'a'≠'c'，全部不同，合法。
24. 26反例 s="aaab"：'a' 有 3 个，超过 limit=2，无论怎么排都有两个 'a' 挨着，所以一开始就返回空串。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def reorganizeString(self, s: str) -> str:
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - 97] += 1
        n = len(s)
        if max(cnt) > (n + 1) // 2:
            return ''
        chars = sorted(range(26), key=lambda i: (-cnt[i], i))
        ans = [''] * n
        idx = 0
        for c in chars:
            for _ in range(cnt[c]):
                if idx >= n:
                    idx = 1
                ans[idx] = chr(c + 97)
                idx += 2
        return ''.join(ans)

#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string reorganizeString(string s) {
        vector<int> cnt(26);
        for (char c : s) cnt[c - 'a']++;
        int n = s.size();
        if (*max_element(cnt.begin(), cnt.end()) > (n + 1) / 2) return "";
        vector<int> order(26);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b){ return cnt[a] == cnt[b] ? a < b : cnt[a] > cnt[b]; });
        string ans(n, ' ');
        int idx = 0;
        for (int c : order) while (cnt[c]--) {
            if (idx >= n) idx = 1;
            ans[idx] = char('a' + c);
            idx += 2;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public String reorganizeString(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        int n = s.length(), max = 0;
        for (int x : cnt) max = Math.max(max, x);
        if (max > (n + 1) / 2) return "";
        Integer[] order = new Integer[26];
        for (int i = 0; i < 26; i++) order[i] = i;
        Arrays.sort(order, (a,b) -> cnt[a] == cnt[b] ? a - b : cnt[b] - cnt[a]);
        char[] ans = new char[n];
        int idx = 0;
        for (int c : order) while (cnt[c]-- > 0) {
            if (idx >= n) idx = 1;
            ans[idx] = (char) ('a' + c);
            idx += 2;
        }
        return new String(ans);
    }
}

复杂度

面试官可能追问