1208 尽可能使字符串相等（滑动窗口）

1. 问题描述：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/get-equal-substrings-within-budget

2. 思路分析：

① 首先是需要理解题目的意思，我们是需要在最大消耗的范围之内求解出最长的子串，可以知道题目的一个很明显的特点是我们在最大消耗规定的范围之内可以扩展子串的右边界的，当扩展的右边界之后发现大于了最大消耗那么这个时候需要将左边界向右边移动，这也就是滑动窗口的基本思想，所以这道题目的本质上是滑动窗口，清楚了题目考察的本质之后那么剩下来的代码就比较简单了

② 滑动窗口都是一些固定的套路，对于这道题目来说我们可以先遍历字符串，使用一个列表来存储两个字符转换的消耗，遍历结束之后再循环中进行右边界与左边界的扩展，当小于了最大消耗扩展右边界，大于了最大消耗扩展左边界，所以可以使用两层循环进行嵌套，最外层的循环用于右边界的扩展，最里面的循环用于左边界的扩展即可

3. 代码如下：

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        slen = len(s)
        cost = []
        for i in range(slen):
            # 计算两个字符之间转换的消耗, 使用ord方法将字符转为ascii码
            cost.append(abs(ord(s[i]) - ord(t[i])))
        l, r, curcost, res = 0, 0, 0, 0
        while r < slen:
            curcost += cost[r]
            # 大于了最大消耗那么需要缩小左边的范围否则增大右边的范围
            while curcost > maxCost:
                # 当大于了最大消耗的时候进行最长长度的更新
                res = max(res, r - l)
                curcost -= cost[l]
                l += 1
            r += 1
        # 有可能是字符串的最大长度
        res = max(res, r - l)
        return res

 

本文地址：https://blog.csdn.net/qq_39445165/article/details/107372088