1208. 尽可能使字符串相等 Medium
给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成t 中对应的子字符串，则返回 0。
示例 1：
输入：s = "abcd", t = "bcdf", maxCost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。
示例 2：
输入：s = "abcd", t = "cdef", maxCost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
示例 3：
输入：s = "abcd", t = "acde", maxCost = 0
输出：1
解释：a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。
解题思路
输入：两个长度相等的字符串 s 和 t
输出：需要将 s 转化成 t ，返回在最大开销的前提下可以转化的最长长度
本题属于 可变长度滑动窗口类型 类型。
我们可以使用双指针维护一个滑动窗口，并用一个变量统计窗口内的开销总数 windowCost。当 windowCost <= maxCost 时，说明当前窗口是合法的，可以更新答案的长度；当超过 maxCost 时，就不断移动左指针缩小窗口，直到重新满足条件。
整个过程中，我们在遍历右指针的同时，动态调整窗口并记录合法窗口的最大长度，最终返回即可。
代码实现
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
left = 0 # 滑动窗口左边界
windowCost = 0 # 当前窗口总修改成本
maxLength = 0 # 满足条件的最长子串长度
for right in range(len(s)):
# 计算当前字符位置的修改成本
cost = abs(ord(s[right]) - ord(t[right]))
windowCost += cost
# 如果窗口总成本超过最大允许值，就收缩左边界
while windowCost > maxCost:
reduceCost = abs(ord(s[left]) - ord(t[left]))
windowCost -= reduceCost
left += 1
# 更新最长长度
maxLength = max(maxLength, right - left + 1)
return maxLength/**
* @param {string} s
* @param {string} t
* @param {number} maxCost
* @return {number}
*/
var equalSubstring = function(s, t, maxCost) {
let left = 0;
let windowCost = 0;
let ans = 0;
for (let right = 0; right < s.length; right ++) {
if (s[right] !== t[right]) {
windowCost += Math.abs(s[right].charCodeAt() - t[right].charCodeAt());
}
while (windowCost > maxCost) {
windowCost -= Math.abs(s[left].charCodeAt() - t[left].charCodeAt());
left ++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)