LeetCode 1208中等滑动窗口
尽可能使字符串相等 图解题解
这道题到底在问什么
等长字符串 s、t，把 s[i] 改成 t[i] 的代价为 |s[i]−t[i]|。在总代价 ≤ maxCost 的前提下，求最长可转换连续子串的长度。
- 输入
- s="abcd", t="bcdf", maxCost=3
- 输出
- 3 （abc→bcd，代价 1+1+1=3）
最优解：一步一步想明白
- 3记住「右扩加和、超预算就左缩减和、每步刷新最长」,下面每一位都在套它。
- 4这一行是每位的代价(s 全 a，t 第 i 位离 a 多远就是 cost[i])。窗口从空开始，右指针从左往右一格格扩。
- 5右指针到第 0 位(t='d'，代价 3)，加进窗口，和变成 3。仍在预算 5 内，窗口合法。
- 6窗口 [0, 0] 合法，长度 1。比之前更长，刷新 ans=1。
- 7右指针到第 1 位(t='b'，代价 1)，加进窗口，和变成 4。仍在预算 5 内，窗口合法。
- 8窗口 [0, 1] 合法，长度 2。比之前更长，刷新 ans=2。
- 9右指针到第 2 位(t='b'，代价 1)，加进窗口，和变成 5。仍在预算 5 内，窗口合法。
- 10窗口 [0, 2] 合法，长度 3。比之前更长，刷新 ans=3。
- 11右指针到第 3 位(t='b'，代价 1)，加进窗口，和变成 6。超了预算 5(红)，需要左缩。
- 12把左指针右移 1 步、依次减掉移出位的代价，窗口和回到 3(≤5)。现在窗口 [1, 3] 长度 3。没超过最长 ans=3。
- 13右指针到第 4 位(t='b'，代价 1)，加进窗口，和变成 4。仍在预算 5 内，窗口合法。
- 14窗口 [1, 4] 合法，长度 4。比之前更长，刷新 ans=4。
- 15右指针到第 5 位(t='b'，代价 1)，加进窗口，和变成 5。仍在预算 5 内，窗口合法。
- 16窗口 [1, 5] 合法，长度 5。比之前更长，刷新 ans=5。
- 17右指针到第 6 位(t='e'，代价 4)，加进窗口，和变成 9。超了预算 5(红)，需要左缩。
- 18把左指针右移 4 步、依次减掉移出位的代价，窗口和回到 5(≤5)。现在窗口 [5, 6] 长度 2。没超过最长 ans=5。
- 19右指针到第 7 位(t='c'，代价 2)，加进窗口，和变成 7。超了预算 5(红)，需要左缩。
- 20把左指针右移 2 步、依次减掉移出位的代价，窗口和回到 2(≤5)。现在窗口 [7, 7] 长度 1。没超过最长 ans=5。
- 21右指针到第 8 位(t='d'，代价 3)，加进窗口，和变成 5。仍在预算 5 内，窗口合法。
- 22窗口 [7, 8] 合法，长度 2。没超过最长 ans=5。
- 23右指针到第 9 位(t='b'，代价 1)，加进窗口，和变成 6。超了预算 5(红)，需要左缩。
- 24把左指针右移 1 步、依次减掉移出位的代价，窗口和回到 4(≤5)。现在窗口 [8, 9] 长度 2。没超过最长 ans=5。
- 25扫完全程，最长的合法窗口是绿色这 5 位(代价和 5 ≤ 5)，所以答案 5。左右指针各只走一遍,O(n)。
⚠️ 容易写错的地方
✗ 错：为每个起点重新算子段和
✓ 对：滑动窗口复用，右加左减
重算是 O(n²)，窗口复用是 O(n)
✗ 错：左缩用 if 只缩一次
✓ 对：用 while 缩到窗口和 ≤ maxCost
一次右扩可能需要左缩多步才合法
✗ 错：边界:maxCost=0 时
✓ 对：只能取连续的 0 代价段;没有 0 代价位则答案为 0
预算 0 时任何正代价都超,只有 cost=0 的位能进窗口;若一个 0 代价位都没有,最长合法窗口长度就是 0
完整代码（Python / C++ / Java）
Python
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
left = cost = ans = 0
for right, (a, b) in enumerate(zip(s, t)):
cost += abs(ord(a) - ord(b))
while cost > maxCost:
cost -= abs(ord(s[left]) - ord(t[left]))
left += 1
ans = max(ans, right - left + 1)
return ansC++
#include <string>
#include <algorithm>
#include <cstdlib>
using namespace std;
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int left = 0, cost = 0, ans = 0;
for (int right = 0; right < (int)s.size(); ++right) {
cost += abs(s[right] - t[right]);
while (cost > maxCost) {
cost -= abs(s[left] - t[left]);
++left;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int left = 0, cost = 0, 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;
}
}复杂度
时间
O(n)
左右指针各只前进一遍
空间
O(1)
只用 left/sum/ans 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 尽可能使字符串相等 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的滑动窗口和「最小覆盖子串」那类有何异同？+
同:都是右扩+条件不满足时左缩的可变长窗口。异:本题求「满足约束(和≤预算)的最长」窗口,左缩发生在「超约束」时;而最小覆盖求「满足约束(覆盖全部)的最短」,左缩发生在「已满足、试图缩短」时。一个求最长、一个求最短,左缩触发条件正好相反。
如果代价可能为负会怎样？+
本题代价是绝对值、恒非负,所以窗口和随右扩单调不减、左缩单调不增,滑动窗口成立。若代价可负,窗口和不再单调,滑动窗口失效,要改用前缀和+单调队列等手段。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 尽可能使字符串相等 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。