原题地址（中等）

方法1—滑动窗口/双指针

思路

这题与前几天的424.替换字符串如出一辙，用的都是同一个思路。

代码

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        cost = [abs(ord(s[i]) - ord(t[i])) for i in range(n)]
        l = r = 0
        maxLen, curCost = 0, 0
        while r < n:
            curCost += cost[r]
            while curCost > maxCost:
                curCost -= cost[l]
                l += 1
            maxLen = max(maxLen, r - l + 1)
            r += 1
        return maxLen

时空复杂度

时间O(N) 空间O(N)，可优化成O(1)

空间O(1)代码

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        i = l = r = maxLen = curCost = 0
        while r < len(s):
            curCost += ( abs( ord(s[r])-ord(t[r]) ) )
            while curCost > maxCost:
                curCost -= ( abs( ord(s[l])-ord(t[l]) ) )
                l += 1
            maxLen = max(maxLen, r - l + 1)
            r += 1
        return maxLen