LeetCode 767. 重构字符串
目录
题目描述
题意分析
给定一个只含小写字母的字符串，要把它的字符重新排列，使排列后任意两个相邻位置上的字符互不相同；做不到就返回空串。注意重排是「多重集合的排列」，每个字符用且仅用原有的次数，不能增删。
题目只关心「相邻不同」，不要求字典序最小，也不要求唯一解，这说明只需要给出任意一个可行排列，属于构造题而非搜索题——一旦有构造方案，就不必枚举全排列。
字符集固定为 26 个小写字母，而串长可达 $500$，说明统计信息只有 $26$ 个计数值，判定与构造都应该围绕这张计数表展开，不必关心字符原本的位置。
关键的可行性边界来自出现最多的那个字符：把它两两隔开至少需要在它们中间塞进「它的个数减一」个别的字符，一旦别的字符不够用就无解。边界情形包括：串长为 $1$ 时必然可行；所有字符都相同且长度大于 $1$ 时必然无解；长度为奇数时最多的字符恰好可以比一半多一个；以及所有字符互不相同这种「随便排都行」的情形。
解法：最高频字符优先填偶数位
核心思路
设字符串长度为
n，最高频字符出现m次。要让它们互不相邻，至少需要m - 1个其他字符放进间隔，因此可行条件是m <= (n + 1) / 2；超过这个上限必然无解。构造时先把最高频字符放到下标
0,2,4,...。这些位置天然相隔至少一格，且可行条件保证它们放得下。随后把其他字符继续填入剩余偶数位，偶数位用完后再填1,3,5,...。最高频字符先被完全摊开，剩余任一字符的次数都不超过它；按“先偶后奇”的位置序列连续填充时，同一字符的落点不会相邻。这个构造同时证明了上述条件的充分性，不需要回溯或反复检查相邻字符。
最大堆也能每次挑选剩余次数最多且不同于上一位的字符，但固定小写字母场景下会多出堆操作。偶、奇下标构造直接利用 26 个字符的固定计数表，时间复杂度更低，证明也更集中。
解题步骤
- 用长度为 26 的数组统计频次，并找到最高频字符。
- 若最高频次大于
(n + 1) / 2，返回空字符串。- 从下标 0 开始，每隔一个位置放入最高频字符。
- 按字母遍历其余计数，继续每隔一个位置写入；位置越界时切换到下标 1。
- 将结果字符数组转成字符串。
例如
"aaabc"中a出现 3 次，恰好达到上限。先得到a_a_a，再把b、c放到奇数位，结果可以是"abaca"。
代码实现
class Solution {
public String reorganizeString(String s) {
int[] count = new int[26];
int maxIndex = 0;
for (char c : s.toCharArray()) {
int index = c - 'a';
count[index]++;
if (count[index] > count[maxIndex]) {
maxIndex = index;
}
}
if (count[maxIndex] > (s.length() + 1) / 2) {
return "";
}
char[] ans = new char[s.length()];
int position = 0;
while (count[maxIndex] > 0) {
ans[position] = (char) ('a' + maxIndex);
position += 2;
count[maxIndex]--;
}
for (int index = 0; index < count.length; index++) {
while (count[index] > 0) {
if (position >= ans.length) {
position = 1;
}
ans[position] = (char) ('a' + index);
position += 2;
count[index]--;
}
}
return new String(ans);
}
}
func reorganizeString(s string) string {
count := [26]int{}
maxIndex := 0
for i := range s {
index := int(s[i] - 'a')
count[index]++
if count[index] > count[maxIndex] {
maxIndex = index
}
}
if count[maxIndex] > (len(s)+1)/2 {
return ""
}
ans := make([]byte, len(s))
position := 0
for count[maxIndex] > 0 {
ans[position] = byte('a' + maxIndex)
position += 2
count[maxIndex]--
}
for index := range count {
for count[index] > 0 {
if position >= len(ans) {
position = 1
}
ans[position] = byte('a' + index)
position += 2
count[index]--
}
}
return string(ans)
}
复杂度分析
- 时间复杂度：$O(n + C)$，其中字符集大小
C = 26；每个字符只统计和写入一次。- 空间复杂度：$O(n + C)$，结果数组占 $O(n)$，计数数组为常数空间。若不计返回结果，额外空间为 $O(C)$。
关键点总结
- 最高频次决定是否可行：
maxCount <= (n + 1) / 2。- 先处理约束最紧的最高频字符，避免最后剩下一批无法分隔的字符。
- 偶数位放完后切换到奇数位，利用位置间隔保证相同字符不相邻。
- 题目只要求任意可行答案，无需追求字典序或使用回溯。
易错点总结
- 判定阈值写成
n / 2会把"aab"误判为无解。- 临界值可行，判断条件必须是
>，不能是>=。- 其他字符应在位置越界时切换到 1，不能覆盖已经填好的下标 0。
- 若不先放最高频字符，某个高频字符可能跨越偶、奇位置的接缝并相邻。
- 计数循环必须保证每次写入后递减，否则会越界或死循环。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 621. 任务调度器 | 中等 | 间隔要求从固定的 $1$ 推广到任意 $n$，且只需算最短总时长而非给出排列 |
| 1405. 最长快乐字符串 | 中等 | 允许同字符连续出现两次，且目标是尽可能长而非用完全部字符 |
| 451. 根据字符出现频率排序 | 中等 | 要求恰好相反——把相同字符聚拢并按频率降序，是排序题不是构造题 |
| 984. 不含 AAA 或 BBB 的字符串 | 中等 | 只有两种字符，限制是不出现三连而非两连，构造靠成对输出而非隔位填充 |
| 1247. 交换字符使得字符串相同 | 中等 | 同为基于计数的贪心，但操作是两串间交换，判据来自不匹配位的奇偶性 |