LeetCode 1156. 单字符重复子串的最大长度
目录
题目描述
题意分析
给一个只含小写字母的字符串
text，最多做一次交换（把两个位置上的字符互换，也可以不换），求交换后能得到的最长的「所有字符都相同」的子串长度。先把「一次交换」这个约束翻译成对答案区间的限制。假设最终那段全同字符的子串由字符
ch组成，占据某个区间。交换只能改动两个位置，其中至多一个落在这个区间内，所以交换前这个区间里最多只能有一个位置不是ch。反过来说，凡是区间内非ch的位置超过一个，一次交换救不回来。这是第一条硬约束。第二条硬约束更隐蔽，也是本题的真正考点：交换只是把两个已有的字符换位置，不会凭空造出新的字符。所以答案长度绝不可能超过
ch在整个字符串中出现的总次数。像aaabaaa这种串，中间的b虽然只有一个、看似换掉就能得到长度 7 的全a串，但全串一共只有 6 个a，那个用来替换b的a必须从区间内部抽走，最终最长只能是 6。这两条约束还需要一次可行性确认：当区间内恰有一个非
ch位置、且区间长度不超过ch的总数时，区间外一定还剩至少一个ch（总数减去区间内的ch个数大于等于 1），拿它和区间内那个异类对调即可，所以两条约束一起就是充要的。字符集只有 26 个小写字母，且字符串长度上限在两万量级，这组数字在提示：可以对每个字母单独跑一遍线性扫描，$26n$ 的代价完全可以接受，不必设计一次扫描同时处理所有字母的复杂结构。
边界：全串同一个字符时答案就是串长；长度为 1 的串答案是 1；某个字母压根没出现时不必为它做任何计算。
解法：枚举目标字符的滑动窗口
核心思路
直接对着原串思考「换哪两个位置」会陷入 $O(n^2)$ 的配对枚举。破局点在于先把答案的目标字符固定下来：如果提前宣布「我要的是一段全
a」，那么「区间内至多一个非a」就变成了一个标准的、单调的窗口约束——窗口越长，里面的非a只会越多，不会越少。有了单调性，就能用左右两个指针一次线性扫描扫出所有极大合法窗口。目标字符只有 26 种，全部枚举一遍即可，于是整体是 26 次独立的线性扫描。
对固定的目标字符
target，维护窗口[left, right]和计数diff表示窗口内不等于target的字符个数。循环不变量是：每次处理完right之后，diff恒等于区间[left, right]内非target字符的个数，且diff <= 1。右指针每前进一格就把新字符计入diff，一旦diff超过 1，就右移left并把移出的字符从diff里扣掉，直到不变量重新成立。因为约束只在窗口变长时可能被破坏、在窗口变短时只会更容易满足，左指针永远不需要回退，所以两个指针都单调右移，每个字符至多进出窗口各一次。
最后把第二条硬约束叠上去：合法窗口的长度
right - left + 1只是「区间形状」允许的上限，还要和freq[target]（该字符全局出现次数）取较小值才是真正可达的长度。答案取所有目标字符、所有合法窗口下这个较小值的最大值。这里有个容易被忽略的细节：不需要专门去找「窗口外是否还有多余的
target」，因为一旦len <= freq[target]，窗口外剩余的target个数至少是freq[target] - (len - 1) >= 1，可换的字符必然存在；取min这一步已经把可行性判断包含进去了。
解题步骤
- 先统计 26 个字母各自的出现次数存进
freq。为什么必须先统计：freq[target]是答案的天花板，而且它是全局信息，边扫边算拿不到，只能预处理。- 外层枚举目标字符
target（0到25）。为什么要枚举：只有先把目标字符钉死，「窗口内最多一个异类」才是一个含义明确、可单调判定的条件；不固定目标字符就无法定义什么叫「异类」。- 跳过
freq[target] == 0的字母。为什么：这个字母根本不在串里，任何窗口对它的贡献都是min(len, 0) = 0，扫一遍纯属浪费。- 每个
target开始前重置left = 0、diff = 0。为什么：两个变量都描述当前这一轮扫描的窗口状态，跨轮复用会让新一轮从上一轮遗留的位置起步，窗口彻底错位。- 右指针推进：
text[right] != target时diff++。为什么只统计异类而不统计同类：约束只压在异类数量上，同类字符个数可以由窗口长度减去diff反推，没必要额外维护。- 收缩：
while (diff > 1)，若text[left]是异类则diff--，然后无条件left++。为什么left++必须写在if外面：窗口最左端也可能正好是目标字符，此时它不影响diff，如果不移动左指针，循环条件永远为真，直接死循环。- 统计答案：
ans = max(ans, min(right - left + 1, freq[target]))。为什么要取min：窗口形状允许的长度未必能被实际拥有的字符数量兑现，这一步是题目「交换不创造字符」这条约束的落地。- 返回
ans。以
text = "ababa"走一遍target = 'a'的扫描。先统计得freq['a'] = 3、freq['b'] = 2。初始left = 0、diff = 0、ans = 0。
right = 0，字符a：是目标字符，diff保持0。窗口[0, 0] = "a"，长度 1，min(1, 3) = 1，ans = 1。
right = 1，字符b：异类，diff = 1，未超限不收缩。窗口[0, 1] = "ab"，长度 2，min(2, 3) = 2，ans = 2。
right = 2，字符a：diff仍是1。窗口[0, 2] = "aba"，长度 3，min(3, 3) = 3，ans = 3。这一步的含义是：把中间的b和串外某个a对调就能得到aaa。
right = 3，字符b：diff = 2，超限，进入收缩。text[0] = 'a'不是异类，diff不变，left变成1；仍然diff = 2，text[1] = 'b'是异类，diff减到1，left变成2。窗口[2, 3] = "ab"，长度 2，min(2, 3) = 2，ans保持3。
right = 4，字符a：diff仍是1。窗口[2, 4] = "aba"，长度 3，min(3, 3) = 3，ans保持3。再跑
target = 'b'，freq['b'] = 2，任何合法窗口的贡献都被min压到最多2，无法刷新ans。最终返回3，即把某个b与某个a对调后得到的aaa。再用
text = "aaabaaa"检验min的作用：target = 'a'、freq['a'] = 6，整串只有一个b，diff始终不超过 1，窗口能一路撑到[0, 6]，长度 7。若不取min会输出 7，但全串统共只有 6 个a，用来顶替b的那个a只能从窗口内部抽调，抽走之后又空出一个洞。取min(7, 6) = 6才是正确答案。
代码实现
class Solution {
public int maxRepOpt1(String text) {
int[] freq = new int[26];
for (int i = 0; i < text.length(); i++) {
freq[text.charAt(i) - 'a']++;
}
int ans = 0;
for (int target = 0; target < 26; target++) {
if (freq[target] == 0) {
continue;
}
int left = 0;
int diff = 0;
for (int right = 0; right < text.length(); right++) {
if (text.charAt(right) - 'a' != target) {
diff++;
}
while (diff > 1) {
if (text.charAt(left) - 'a' != target) {
diff--;
}
left++;
}
// 一次交换最多填掉一个非目标字符，长度还不能超过目标字符总数。
int len = right - left + 1;
ans = Math.max(ans, Math.min(len, freq[target]));
}
}
return ans;
}
}
func maxRepOpt1(text string) int {
freq := make([]int, 26)
for i := 0; i < len(text); i++ {
freq[text[i]-'a']++
}
ans := 0
for target := 0; target < 26; target++ {
if freq[target] == 0 {
continue
}
left := 0
diff := 0
for right := 0; right < len(text); right++ {
if int(text[right]-'a') != target {
diff++
}
for diff > 1 {
if int(text[left]-'a') != target {
diff--
}
left++
}
// 一次交换最多填掉一个非目标字符，长度还不能超过目标字符总数。
length := right - left + 1
if length > freq[target] {
length = freq[target]
}
if length > ans {
ans = length
}
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(26n)$，即 $O(n)$。预处理频次是一遍 $O(n)$；外层枚举 26 个目标字符，每轮内层扫描中左右指针都只单调右移、各自至多走过
n个位置，while收缩的总步数被left的总位移量摊还，所以每轮是 $O(n)$ 而非 $O(n^2)$。- 空间复杂度：$O(1)$，只有一个长度固定为 26 的计数数组和几个标量，与输入长度无关；没有用哈希表存下标列表，也没有构造任何新字符串。
关键点总结
- 遇到「最多改动 k 处后求最长同质区间」，先把目标值固定下来，约束才会变成单调条件，滑动窗口才用得上；这是本题从 $O(n^2)$ 配对枚举降到线性的关键转折。
- 「交换不创造新字符」这条全局守恒约束必须单独用
freq兜住，它不是窗口内的局部性质，窗口逻辑本身永远发现不了它——面试中能主动说出aaabaaa这个反例，基本就说明想透了。- 取
min(len, freq[target])同时完成了「封顶」和「可行性验证」两件事，因为len <= freq[target]已经蕴含了窗口外还剩至少一个目标字符可供交换，无需再写额外判断。- 滑动窗口的收缩里，指针推进必须无条件执行，只有计数的增减才受字符判定控制，二者混在同一个
if里是死循环的常见来源。- 字符集大小是常数时，「对每个字符各跑一遍线性扫描」是完全合法的设计，$O(26n)$ 在面试里应当明确说成 $O(n)$ 并解释常数来源，而不是含糊带过。
易错点总结
- 忘记和
freq[target]取min："aaabaaa"会输出7，但全串只有 6 个a，正确答案是6；这是本题第一大坑。- 误用
max(len, freq[target])："ab"时目标a的窗口长度是 2、freq['a']是 1，会输出2，而只有一个a时答案只能是1。- 只统计现成的最长连续同字符段：
"ababa"里最长同字符段长度是1，会输出1，正确答案是3。- 收缩条件写成
while (diff > 2)：等于允许一次交换修好两个位置。"aabbaa"会得到min(6, 4) = 4，而实际最优只能是3。left++写在if内部，只在扣减diff时才推进："baa"中目标为b时，right = 2触发收缩而text[0] = 'b'不是异类，diff不减、left不动，while条件恒真，程序死循环。- 比较时忘记
- 'a'，用字符直接和下标比：'a'的码值是 97，永远不等于下标0，"aaa"里每个字符都被判成异类，窗口被压到长度 1，输出1。left和diff定义在枚举target的循环外面：换目标字符时left仍停在上一轮结束的位置，新一轮开头会算出right - left + 1为负数的窗口，统计彻底失真。- 收缩时扣减的是
text[right]而不是text[left]：diff与窗口真实内容脱节，窗口只会一路变长。"aaabbaaa"目标为a时窗口能撑到整串长度 8，输出min(8, 6) = 6，而正确答案是4。- 改用「按字符记录下标、合并相邻两段」的写法却漏掉总数封顶：
"aabaa"的两段aa隔着一个b，合并后算出5，但只有 4 个a，正确答案是4。- 认为不交换就不算答案，强制必须换一次：
"aaaa"会被误判成需要打散再拼，输出小于4；题目允许「最多一次」，包括一次都不换。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 424. 替换后的最长重复字符 | 中等 | 可替换 k 个字符且字符凭空产生，没有本题的总数封顶 |
| 1004. 最大连续1的个数 III | 中等 | 二值版本，翻转 k 个 0 而不是交换，同样无需考虑资源守恒 |
| 487. 最大连续1的个数 II | 中等 |
k = 1 的二值特例，窗口约束与本题的 diff <= 1 完全同构 |
| 1493. 删掉一个元素以后全为 1 的最长子数组 | 中等 | 操作是删除而非交换，最终长度要在窗口长度上再减 1 |
| 485. 最大连续 1 的个数 | 简单 | 不允许任何修改，退化成一次遍历数段落，是本题的基线 |
| 3. 无重复字符的最长子串 | 中等 | 窗口约束是「无重复」，需要哈希记录字符最近位置而非计数 |
| 340. 至多包含 K 个不同字符的最长子串 | 中等 | 约束落在「不同字符种类数」上，收缩时要维护每种字符的剩余个数 |
| 159. 至多包含两个不同字符的最长子串 | 中等 | 340 的 k = 2 特例，可用两个变量替代哈希表 |
| 1208. 尽可能使字符串相等 | 中等 | 窗口约束是代价总和不超预算，收缩条件从计数变成求和 |
| 1151. 最少交换次数来组合所有的 1 | 中等 | 同样是交换聚合，但交换次数不限、窗口长度固定，求的是最少操作数 |