问题描述
给你两个长度相同的字符串，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。
解题过程
- 首先分析一下题干内容，要求将一个字符串里的子串转换成另一个字符串，并且差值不能大于maxCount，找出能转换的最大子串。
- 使用滑动窗口进行解决，条件是当前差值不大于max的时候，right右移，当前值大于max的时候，整体窗口移动 right++ left++
- 具体解析如下
- 后续进行第二版优化
答案
//第一个版本（10ms执行时间，打败28%）
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
//区间右边界
int right = 0;
//区间左边界
int left = 0;
//当前区间内替换差总数
int count = 0;
//右边界未达到末尾
while(right < s.length()){
//TODO 计算出右侧新增的差值
int abs = Math.abs(s.charAt(right) - t.charAt(right));
//不管什么，直接加到总数里
count += abs;
if(count <= maxCost){
//如果总数小于最大值，继续扩张右侧窗口
right++;
}else{
//如果总数超过了最大值，则将左侧的差值去除，并右滑窗口
count -= Math.abs(s.charAt(left) - t.charAt(left));
left++;
right ++;
}
//System.out.println("count"+count+";"+left+"---"+right);
}
return right - left;
}
}
从执行结果来看，以上执行效率很低，于是我们思考对其进行优化，首先，从整体来看，进行了一个right = [0,n]的循环，内部没有嵌套循环了，看上去整体思路应该是比较优的了，那么接着从细节分析，
- while判断条件，每次都需要执行s.length()方法获取字符串的长度，(虽然s.length()并不会占用太多时间，)
- Math.abs(s.charAt(right) - t.charAt(right));在循环中操作了2次，这个可以使用一个新的int数组进行存储
- 最终效果如下
//第二个版本（4ms执行时间，打败99%）
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
//区间右边界
int right = 0;
//区间左边界
int left = 0;
//当前区间内替换差总数
int count = 0;
//数组长度
int length = s.length();
//使用数组一次性存储差异，防止后续重复计算
int diff[] = new int[length];
//该处时间复杂度O(n)
for(int i=0;i<length;i++){
diff[i] = Math.abs(s.charAt(i) - t.charAt(i));
}
//右边界未达到末尾,该处时间复杂度O(n)
while(right < length){
count += diff[right];
right++;
if(count > maxCost){
count -= diff[left];
left++;
}
//System.out.println("count"+count+";"+left+"---"+right);
}
return right - left;
}
}
