https://leetcode.cn/problems/get-equal-substrings-within-budget/description/
滑动窗口,固定的套路是,固定右端点枚举,缩小左端点维护合法的窗口状态,在维护使得合法后
(状态变化具有单调性,即扩大区间,状态是单调变化的),左端点是满足合法性质的最右点了,才更新答案
class Solution {public int equalSubstring(String S, String T, int maxCost) {int res=0;int cost=0;char[] s=S.toCharArray();char[] t=T.toCharArray();// 滑动窗口,固定的套路是,固定右端点枚举,缩小左端点维护合法的窗口状态,在维护使得合法后// (状态具有单调性,即扩大区间,状态是单调变化的),左端点是满足合法性质的最右点了,才更新答案// 数据范围上看可以使用滑动窗口,最大长度,意味着花费尽可能多,有贪心的思想for(int i=0,j=0;i<s.length;i++){cost+=Math.abs(s[i]-t[i]);while(cost>maxCost){cost-=Math.abs(s[j]-t[j]);j++;}res=Math.max(res,i-j+1);}return res;}
}