题目大意：
尽可能使字符串相等
给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] – t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
示例 1：
输入：s = "abcd", t = "bcdf", cost = 3 输出：3 解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。
示例 2：
输入：s = "abcd", t = "cdef", cost = 3 输出：1 解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
示例 3：
输入：s = "abcd", t = "acde", cost = 0 输出：1 解释：你无法作出任何改动，所以最大长度为 1。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1208
解题思路分析：
我们可以先把两个字符串的每一位对比一下，看一下他们的差值各是多少，将每一位的差（cost）存入数组。这样问题就转化为在cost数组中找到一个最长的连续子数组，其和小于等于题目给出maxCost。这一步的处理需要用到sliding-window，初始时，sliding-window的左边和右边均在第0位，先向右移动右边扩大区间范围，并查看区间内的和，如果和小于等于maxCost，此时区间长度为一个候补解，继续向右移动右边。如果和大于maxCost，则向右移动左边，缩小区间范围，并查看区间内的和，重复以上步骤，直到数组循环结束，找到最大候补解即是答案。
看下完整实现代码：
public int equalSubstring(String s, String t, int maxCost) {
int[] cost = new int[s.length()]; // 定义cost数组
for(int i=0;i<s.length();i++){ // 记录字符串s和t每一位的cost差值
cost[i] = Math.abs(s.charAt(i)-t.charAt(i));
}
// sum为区间和。startIndex为左边。maxLength为最大区间
int sum=0,startIndex=0,maxLength=0;
for(int i=0;i<s.length();i++){ // 循环cost数组
sum+=cost[i]; // 累加当前区间总和（cost）
if(sum<=maxCost){ // 区间总和小于等于maxCost时为一个候补解
// 更新区间最大长度
maxLength = Math.max(i-startIndex+1, maxLength);
}else{ // 区间总和小于maxCost
sum-=cost[startIndex]; // 区间和减去最左边的数字
startIndex++; // 向右移动左边
}
}
return maxLength; // 返回最大区间
}本题解法运行时间为4ms。
Runtime: 4 ms, faster than 98.58% of Java online submissions for Get Equal Substrings Within Budget.
Memory Usage: 36.8 MB, less than 100.00% of Java online submissions for Get Equal Substrings Within Budget.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1208-get-equal-substrings-within-budget-解题思路分析/