【力扣】（中等）1208. 尽可能使字符串相等 --- 双指针

• 1208 尽可能使字符串相等

• 给你两个长度相同的字符串，s 和 t。

  将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

  用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

  如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

  如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

  来源：力扣（LeetCode）

  链接：https://leetcode-cn.com/problems/get-equal-substrings-within-budget

• 【解题思路】双指针：利用left，right左右指针来维护子字符串的长度，右指针right从0开始，计算左指针到右指针之间字符串的差值总和sum，每次循环right右移一次直至达到s字符串的末尾。当该长度总和sum>maxCost时，左指针left右移直至sum<=maxCost为止。记录每次子字符串长度，取最大值返回即可。

• 最开始想用哈希表记录差值，sum为总差值，从最大差值递减遍历，直至sum<maxCost，问题是忽略了字符串的顺序性。

// c++
class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int len = s.size();
        vector<int> abs_val(len,0);
        for(int i=0; i<len; ++i){
            abs_val[i] = abs(s[i]-t[i]);
        }
        int left=0,right=0,sum=0,result=0;
        while(right<len){
            sum += abs_val[right];
            while(sum>maxCost){
                sum-=abs_val[left];
                ++left;
            }
            result = max(result,right-left+1);
            ++right;
        }
        return result;
    }
};