问题描述

给你两个长度相同的字符串，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。

解题过程

1. 首先分析一下题干内容，要求将一个字符串里的子串转换成另一个字符串，并且差值不能大于maxCount，找出能转换的最大子串。
2. 使用滑动窗口进行解决，条件是当前差值不大于max的时候，right右移，当前值大于max的时候，整体窗口移动 right++ left++
3. 具体解析如下
4. 后续进行第二版优化

答案

//第一个版本（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]的循环，内部没有嵌套循环了，看上去整体思路应该是比较优的了，那么接着从细节分析，

1. while判断条件，每次都需要执行s.length()方法获取字符串的长度，(虽然s.length()并不会占用太多时间，)
2. Math.abs(s.charAt(right) - t.charAt(right));在循环中操作了2次，这个可以使用一个新的int数组进行存储
3. 最终效果如下

//第二个版本（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;
    }
}