LeetCode 1417. 重新格式化字符串
目录
题目描述
题意分析
给定一个只含小写字母和数字的字符串
s，要把它重新排列成「没有两个相邻字符类型相同」的形式——也就是字母和数字必须严格交替出现。返回任意一个合法排列；若不存在这样的排列，返回空串。「重新排列」意味着字符的多重集合不变，只能改顺序，不能增删也不能替换。所以每个字符具体是什么其实无关紧要，真正决定成败的只有两个数：字母的个数和数字的个数。
「类型不同」只区分「字母」与「数字」两类，同为字母的
'a'和'b'相邻是允许的吗？不允许——它们类型相同。这一点必须读准：约束的是类型，不是具体字符。由此可以立刻推出可行性条件。合法串必然是两类字符严格交替的序列，形如
ABABAB...。设两类的个数分别是p和q，交替排列要求|p - q| <= 1：相等时两种起始方式都行，相差 1 时必须由多的那一类打头且由它收尾，相差 2 及以上时无论怎么排都会出现同类相邻。约束里
s长度在 1 到 500 之间，只含小写字母和数字。规模极小，线性做法轻松通过。边界要留意四点：全是字母或全是数字时（长度大于 1）必然无解；长度为 1 时无论哪类都合法，直接返回原串；两类数量相等时结果的起始类型可以任选；数量相差 1 时起始类型被唯一确定。
解法：双队列交替拼接
核心思路
原顺序可以任意打乱，真正影响可行性的只有字母数
letters和数字数digits。严格交替的类型骨架只能是“字母、数字、字母……”或反过来。可行的充要条件是两类数量之差的绝对值不超过 1。必要性来自交替串的奇偶位置数至多相差 1；充分性则由直接构造给出：让数量较多的一类作为
first，另一类作为second，依次追加first[i]，若存在再追加second[i]。构造不变量是：每轮结束后，已写入字符严格交替，两组都恰好消费前
i+1个字符，或者较短组少消费最后一个；因为first只可能与second等长或多 1，短组耗尽只会发生在最后，剩余的一个first可以合法收尾。因此算法不会漏字符、不会重复字符，也不会产生相邻同类字符。若数量差大于 1，任何排列都至少有两个多数类字符相邻，返回空串。
解题步骤
- 扫描
s，把数字和字母分别放入两个缓冲区。- 若两组长度差的绝对值大于 1，返回空串。
- 把较长组设为
first；等长时任选字母组在前。- 遍历
first：先追加first[i]，若i < second.length再追加second[i]。- 返回构造结果。
例如
s = "covid2019"，字母 5 个、数字 4 个，字母组在前可得到"c2o0v1i9d"。"ab123"必须由数字开头，可得到"1a2b3"。"1229857369"的两类数量差大于 1，必定无解。长度为 1 时，较长组只有一个字符，循环自然返回原串；两组等长时两种起始类型都合法。
代码实现
class Solution {
public String reformat(String s) {
StringBuilder letters = new StringBuilder();
StringBuilder digits = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= '0' && c <= '9') {
digits.append(c);
} else {
letters.append(c);
}
}
if (Math.abs(letters.length() - digits.length()) > 1) {
return "";
}
StringBuilder first = letters;
StringBuilder second = digits;
if (digits.length() > letters.length()) {
first = digits;
second = letters;
}
StringBuilder answer = new StringBuilder(s.length());
for (int i = 0; i < first.length(); i++) {
answer.append(first.charAt(i));
if (i < second.length()) {
answer.append(second.charAt(i));
}
}
return answer.toString();
}
}
func reformat(s string) string {
letters := make([]byte, 0)
digits := make([]byte, 0)
for i := 0; i < len(s); i++ {
if s[i] >= '0' && s[i] <= '9' {
digits = append(digits, s[i])
} else {
letters = append(letters, s[i])
}
}
if len(letters)-len(digits) > 1 || len(digits)-len(letters) > 1 {
return ""
}
first, second := letters, digits
if len(digits) > len(letters) {
first, second = digits, letters
}
answer := make([]byte, 0, len(s))
for i := 0; i < len(first); i++ {
answer = append(answer, first[i])
if i < len(second) {
answer = append(answer, second[i])
}
}
return string(answer)
}
复杂度分析
- 时间复杂度：$O(n)$。分组扫描和交替构造各访问每个字符一次。
- 空间复杂度：$O(n)$。两个分组缓冲区合计保存 $n$ 个字符；返回结果也需要 $O(n)$。不计输出仍为 $O(n)$。
关键点总结
- 先由合法串的交替骨架推出数量差至多为 1，再进行构造。
- 数量较多的类型必须开头；数量相等时任选一种类型开头。
- 将两组统一成
first和second后，只需一个循环，不需要三段条件拼接。- 每个字符从输入进入一个分组，再进入输出一次，原字符多重集合保持不变。
- 输入只含小写字母和数字，按
'0' <= c <= '9'分类即可。
易错点总结
- 只允许两组数量相等：
"covid2019"的数量差为 1，仍可构造合法结果。- 固定让字母开头：
"ab123"中数字更多，会留下两个相邻数字；多数类必须开头。- 不取绝对差：全字母字符串可能因负差值绕过无解判断；两个方向都要检查。
- 交替循环只遍历较短组：会漏掉多数类最后一个字符，输出不再是原串的重排。
- 把“同类型”误解为“同字符”：任意两个字母相邻都违规，并非只有相同字母才违规。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 767. 重构字符串 | 中等 | 类别从两类升到 26 类，可行性判据变成「最多那类不超过 ⌈n/2⌉」，需要堆 |
| 1405. 最长快乐字符串 | 中等 | 允许两连不允许三连，且不要求用完全部字符，改为贪心求最长 |
| 621. 任务调度器 | 中等 | 同类之间需要固定间隔，可由「最多那类」直接推出总时长公式 |
| 280. 摆动排序 | 中等 | 要求相邻元素大小交替，可一趟扫描按奇偶位就地交换 |
| 324. 摆动排序 II | 中等 | 严格不等的摆动，需要先找中位数再按虚拟下标穿插，边界远比本题复杂 |
| 75. 颜色分类 | 中等 | 三类元素的原地分组，三指针一趟完成，是「按类别重排」的另一形态 |
| 41. 缺失的第一个正数 | 困难 | 同样先想清楚「合法结果长什么样」再反推构造，原地哈希是关键 |
| 443. 压缩字符串 | 中等 | 原地改写字符串，训练读写指针分离的写法 |
| 345. 反转字符串中的元音字母 | 简单 | 按类别筛选后再处理，与本题「先分组再拼接」思路一致 |
| 917. 仅仅反转字母 | 简单 | 只对某一类字符做变换而保持另一类位置不动，是分类处理的入门题 |
| 151. 反转字符串中的单词 | 中等 | 字符串重组的经典题，重点在多余空格与边界的处理 |
| 557. 反转字符串中的单词 III | 简单 | 按分隔符切分后逐段处理，是字符串重排的基本功 |
| 1328. 破坏回文串 | 中等 | 同为「先判可行性再构造」的字符串题，重点是字典序最小 |
| 409. 最长回文串 | 简单 | 靠奇偶计数直接推出答案长度，展示「计数即可解」的思路 |