LeetCode 1208. 尽可能使字符串相等
目录
题目描述
题意分析
给两个等长字符串
s和t，把s[i]改成t[i]的开销是两个字符 ASCII 码差的绝对值。在总开销不超过maxCost的前提下，求能让s的某个子串与t的对应子串完全相同的最长子串长度。第一步要看穿的是：每个下标的开销是互相独立、事先就确定的常量，与选了哪个区间无关。所以整道题可以立刻剥掉字符串的外壳，等价成——给定一个数组
cost[i] = |s[i] - t[i]|，求和不超过maxCost的最长连续子数组的长度。题面里的「字符串」「ASCII」只是包装。转化之后，约束里最要紧的一条浮出水面：
cost[i]恒为非负数（绝对值必然 ≥ 0）。这条性质意味着区间和关于区间的包含关系是单调的——区间往右扩一格，和只增不减；往左缩一格，和只减不增。「非负 + 求满足和的上界约束的最长连续段」这个组合，是双指针能成立的全部理由。另一个信号是「连续子串」而非「子序列」，答案只由左右两个端点决定，因此可以按右端点分类枚举，对每个右端点只保留最优的左端点，这是把 $O(n^2)$ 压成 $O(n)$ 的着力点。
边界要想清楚三处：
maxCost可能为 0，此时只有那些本来就相等的位置能入选；答案可能为 0（每个位置的开销都超预算）；maxCost最大 $10^4$，而单个位置开销最大 25，累加不会溢出，不必上 64 位。
解法：滑动窗口维护预算
核心思路
暴力做法是枚举左右端点：外层定左端点，内层往右扩并累加开销，一旦超预算就停，记录长度。这是 $O(n^2)$，
n达到 $10^5$ 时是 $10^{10}$ 次操作，必然超时。瓶颈在于大量重复的累加：以
left = 0试到right = k停下后，left = 1又从头把[1, k]重新加了一遍。同一段和被反复计算了 $O(n)$ 次。关键观察来自开销的非负性。设
R(l)为「以l为左端点、总开销不超预算所能到达的最远右端点」。因为把左端点右移只会去掉一个非负数、让窗口和变小或不变，所以窗口只会更宽松，于是R(l)关于l单调不减。既然右端点不会倒退，就没必要为每个左端点重新扫一遍——让左右两个指针都只往右走，各自最多走n步，总代价降到 $O(n)$。反过来按右端点组织更好写：对每个右端点
right，我们要的是最小的合法左端点L(right)，这样窗口最长。同样由非负性，L(right)也随right单调不减，所以left指针一路向右推进即可，永不回退。循环不变量：在每轮的答案更新时刻，窗口
[left, right]满足两条——(1) 窗口内开销之和cost$\le$maxCost；(2)left是使条件 (1) 成立的最小左端点，也就是说[left - 1, right]一定超预算（left = 0时该条件空真）。有了这两条，right - left + 1就是以right结尾的最长合法子串长度，对所有right取最大值就是全局答案。维护不变量只需两个动作：
right右移时把cost[right]加进cost（可能破坏条件 1）；然后while (cost > maxCost)不断从左侧吐出元素（恢复条件 1，且因为是「刚好停下」所以同时保证了条件 2 的最小性）。
解题步骤
- 初始化
left = 0、cost = 0、ans = 0。ans初值必须是 0 而不是 1：可能一个字符都改不起（maxCost = 0且处处不等），此时答案就是 0。- 外层枚举右端点
right，先把|s[right] - t[right]|累加进cost。为什么是「先加后收缩」：我们要维护的是「以当前right结尾」的窗口，右端点必须先真正进入窗口，才谈得上判定它是否超预算。- 用
while而不是if收缩左端。为什么必须是while：新加入的这一个字符开销最大可达 25，而左侧可能有一串开销为 0 的位置，一次收缩不足以把cost压回预算内，必须循环到合法为止。写成if只在「每个元素都是 0/1」的题里侥幸正确，本题会直接错。- 收缩条件写
cost > maxCost而非>=。为什么：题目允许开销恰好等于maxCost，等号情况下的窗口是合法的，用>=会把最优解主动踢掉。- 在收缩之后再更新答案
ans = max(ans, right - left + 1)。为什么顺序不能反：收缩前的窗口可能是超预算的非法状态，用它更新会得到虚高的长度。- 返回
ans。循环走完时每个右端点都被作为结尾考察过一次，由不变量可知每次考察拿到的都是该结尾下的最优长度，所以最大值就是全局最优。以
s = "abcd"、t = "bcdf"、maxCost = 3走一遍。先算开销数组：|a-b| = 1、|b-c| = 1、|c-d| = 1、|d-f| = 2，即cost = [1, 1, 1, 2]。
right = 0：cost累加为 1，不超 3，窗口[0, 0]，长度 1，ans = 1。right = 1：cost = 2，不超预算，窗口[0, 1]，长度 2，ans = 2。right = 2：cost = 3，恰好等于预算——这里正是>与>=的分水岭，用>判定则不收缩，窗口[0, 2]，长度 3，ans = 3。right = 3：cost = 3 + 2 = 5 > 3，进入收缩：吐出left = 0的开销 1，cost = 4，仍超预算；再吐出left = 1的开销 1，cost = 3，合法，此时left = 2。窗口[2, 3]，长度 2，ans保持 3。注意这一轮while循环了两次，若写成if就会停在cost = 4的非法窗口上，算出长度 3 并让后续状态全错。- 循环结束，返回
3，对应把"abc"改成"bcd"，总开销恰好 3。再看一个退化用例
s = "a"、t = "z"、maxCost = 0：cost = 25 > 0，收缩把left推到 1，窗口长度0 - 1 + 1 = 0，ans保持 0。可见left越过right时长度自动算成 0，不需要任何特判。
代码实现
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int left = 0;
int cost = 0;
int ans = 0;
for (int right = 0; right < s.length(); right++) {
cost += Math.abs(s.charAt(right) - t.charAt(right));
// 窗口始终维护为总成本不超过预算的最长后缀。
while (cost > maxCost) {
cost -= Math.abs(s.charAt(left) - t.charAt(left));
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
func equalSubstring(s string, t string, maxCost int) int {
left := 0
cost := 0
ans := 0
for right := 0; right < len(s); right++ {
cost += absByteDiff(s[right], t[right])
// 窗口始终维护为总成本不超过预算的最长后缀。
for cost > maxCost {
cost -= absByteDiff(s[left], t[left])
left++
}
if right-left+1 > ans {
ans = right - left + 1
}
}
return ans
}
func absByteDiff(a byte, b byte) int {
if a >= b {
return int(a - b)
}
return int(b - a)
}
复杂度分析
- 时间复杂度：$O(n)$，
n为字符串长度。凭什么：right由外层循环单调走n步；left只在内层while里递增且从不回退，全程最多也走n步。虽然while嵌在for里，但内层总执行次数由left的总位移量决定，是摊还的 $O(n)$ 而非 $O(n^2)$。- 空间复杂度：$O(1)$。凭什么：只用了
left、cost、ans三个标量；开销数组是「按需现算」而非预先物化的，省掉了一个 $O(n)$ 的数组。
关键点总结
- 先剥包装再选算法：本题的字符串外壳可以一眼换成「非负数组求和受限的最长连续段」，转化完成后解法自明。面试时先说出这个等价转化，比直接写代码更能体现建模能力。
- 双指针不回退的合法性来自单调性，而单调性来自元素非负。面试官追问「为什么
left可以不回头」时，标准答案是「因为右移left只会减小窗口和，所以每个右端点的最小合法左端点单调不减」——把这句话说出来，比说「滑窗模板」有分量得多。- 收缩用
while而非if是这类题的通用铁律：新元素的量级可能远大于单个旧元素，一次收缩未必够。只有在「每步增量至多 1」的特殊题里if才恰好等价。- 「不超过预算」类判定要盯死等号方向：
>与>=一字之差，直接决定最优解是否被误杀。写之前先默念一遍题面里是「不超过」还是「小于」。- 答案更新必须发生在窗口恢复合法之后——先修复不变量，再读取不变量，这是所有滑窗代码的固定顺序。
- 本题也可以用「前缀和 + 二分」在 $O(n \log n)$ 内做（前缀和非降，故可二分找最小左端点），但既然双指针能到 $O(n)$，面试首选双指针，把二分作为「还有别的思路吗」的备选答案。
易错点总结
- 收缩用
if代替while：s = "abcd"、t = "bcdf"、maxCost = 3走到right = 3时cost = 5，一次收缩只降到 4，窗口仍非法，却按[1, 3]算出长度 3，若此时真实最优是 2 就会输出偏大的答案；开销跨度更大的数据上错得更明显。- 收缩条件写成
cost >= maxCost：上例right = 2时cost恰好等于 3，本该保留窗口[0, 2]得到答案 3，却被强行收缩到[1, 2]，最终输出 2。- 在收缩之前更新答案：
right = 3时窗口[0, 3]的开销是 5 已经超预算，却用它算出长度 4 并写进ans，返回 4 而正确答案是 3。ans初值设成 1：s = "a"、t = "z"、maxCost = 0时一个字符都改不动，正确答案是 0，却返回 1。- 收缩时忘记从
cost里减去左端开销、只做left++：cost只增不减，第一次超预算后while会把left一路推到越界，Java 抛StringIndexOutOfBoundsException，Go 直接 panic。- 减的是
right位置的开销而不是left位置的：cost = [1, 1, 1, 2]在right = 3时会反复减 2，cost变成 3 后停下但left只前进一步，窗口[1, 3]的真实开销是 4，超预算却被当成合法，答案偏大。- 写成
Math.abs(s.charAt(right)) - Math.abs(t.charAt(right))：括号位置错了，绝对值套在单个字符上恒等于它自身，差值可能为负，cost被越加越小甚至变负，while永不触发，直接返回n。- 误以为可以对开销数组排序后贪心取小的：
cost = [5, 1, 1, 5]、maxCost = 2时排序贪心会选出两个 1 并报长度 2，但它们在原数组里就是相邻的下标 1、2，这次侥幸对；换成cost = [1, 5, 1]、maxCost = 2就会报 2，而真实答案是 1——子串必须连续，排序破坏了下标关系。- 用前缀和 + 二分却把二分方向写反：前缀和数组非降，要找的是最小的
l使pre[right + 1] - pre[l] <= maxCost，等价于pre[l] >= pre[right + 1] - maxCost，即「第一个不小于某值的位置」；写成「最后一个不大于」会得到最短窗口而不是最长窗口，maxCost很大时答案退化成 1。- Go 里把字符串转成
[]rune再比较：题目保证只有小写英文字母，按字节访问即可；转rune白白多出 $O(n)$ 空间，且在 ASCII 场景下语义完全一致，属于无意义开销。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 209. 长度最小的子数组 | 中等 | 同为非负数组 + 和的约束，但求最短满足下界的窗口，收缩时机相反 |
| 1004. 最大连续1的个数 III | 中等 | 预算是「翻转 0 的次数」，等价于本题中开销只取 0/1 的特例 |
| 424. 替换后的最长重复字符 | 中等 | 窗口代价依赖「窗口内最高频字符」，是动态量，需额外维护计数数组 |
| 1493. 删掉一个元素以后全为 1 的最长子数组 | 中等 | 预算固定为删一个 0，且最终长度要减 1，边界处理与本题不同 |
| 3. 无重复字符的最长子串 | 中等 | 约束是「窗口内元素互异」而非数值求和，靠哈希表判定而不是累加器 |
| 904. 水果成篮 | 中等 | 约束是「窗口内至多两种元素」，收缩依据是种类数，需要计数表配合 |
| 713. 乘积小于 K 的子数组 | 中等 | 元素为正保证乘积单调，但统计的是子数组个数，每轮累加窗口长度 |
| 1658. 将 x 减到 0 的最小操作数 | 中等 | 需先把「删两端最少个数」反向转成「求中间和为定值的最长窗口」才能滑窗 |