You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.
You are also given an integer maxCost.
Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.
If there is no substring froms that can be changed to its corresponding substring from t, return 0.
Example 1:
Input:s = "abcd", t = "bcdf", maxCost = 3Output:3Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.
Example 2:
Input:s = "abcd", t = "cdef", maxCost = 3Output:1Explanation: Each character in s costs 2 to change to charactor int, so the maximum length is 1.
Example 3:
Input:s = "abcd", t = "acde", maxCost = 0Output:1Explanation: You can't make any change, so the maximum length is 1.
Constraints:
1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s andt only contain lower case English letters.
思路：
用队列记录连续子数组，当队列中的数据的和大于最大值时，反复出队，直到队列中的数值小于等于最大值或者队列为空。
细节1:出队时，判断队列为空。
细节2:若队列为空，push当前值数据时，需要判断位置的差是否小于等于最大值。示例代码如下：
intequalSubstring(strings,stringt,intmaxCost) {
vector<int> diffval(s.size() +1,0);
for(inti =1; i <= s.size(); i++) {
diffval[i] =abs(s[i-1]-t[i-1]);
}
queue<int>dp;
intcur =0;
intresult =0;
for(inti =1; i <= s.size(); i++) {
intdiff = diffval[i];
if(diff + cur > maxCost) {
while(diff + cur > maxCost && dp.size()) {
intval = dp.front();
cur -= diffval[val];
dp.pop();
}
if(diff + cur <= maxCost) {
dp.push(i);
cur += diff;
}
}else{
dp.push(i);
cur += diff;
}
result =max(result, (int)dp.size());
}
return result;
}
