题目链接

https://leetcode.com/problems/get-equal-substrings-within-budget/

题目描述

给定两个长度相同的字符串s和t。将s[i]变为t[i]需要|s[i]-t[i]|的开销（开销可能为0），即两个字符ASCII码值的差的绝对值。用于变更字符串的最大预算是maxCost，在转化字符串时，总开销应当小于等于该预算。如果可以将s的某个子串转化为t中对应的子串，返回可以转化的最大长度。如果s中没有子字符串可以转化成t中对应的子字符串，则返回0。

示例

输入：s = "abcd",t = "bcdf"，maxCost = 3

输出：3

s中的"abc"可以变为"bcd"，开销为3，所以最大长度为3。

解题思路

由于题目找开销小于等于预算的前提下能够转化的最大长度，我们可以新建数组diff，令diff[i] = |s[i] - t[i]|。那么这个问题就转化为在diff数组中找元素和不超过maxCost的最长子数组长度。

此题可以由滑动窗口来求解，如果窗口内元素和不超过maxCost，则窗口继续扩张；如果超过了maxCost，就收缩直到窗口合法，然后继续扩张......

Python实现

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        diff = []
        for i in range(len(s)):
            diff.append(abs(ord(s[i])-ord(t[i])))
        left,right = 0,0
        res = 0
        curCost = 0
        while(right < len(diff)):
            s = diff[right]
            right += 1
            curCost += s #curCost为当前窗口内的元素和
            while(curCost > maxCost):
                d = diff[left]
                left += 1
                curCost -= d
            res = max(res,right-left)
        return res
        

进一步优化

我们不维护滑动窗口内子串的合法性，只让滑动窗口长度维护当前最长的合法子串。如果滑动窗口内子串合法，滑动窗口就继续扩张。如果不合法，滑动窗口就平移，直到右指针到达数组末尾。

Python实现

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        diff = []
        for i in range(len(s)):
            diff.append(abs(ord(s[i])-ord(t[i])))
        left,right = 0,0
        curCost = 0
        while(right < len(diff)):
            s = diff[right]
            right += 1
            curCost += s #curCost为当前窗口内的元素和
            if(curCost > maxCost):
                d = diff[left]
                left += 1
                curCost -= d
        return right-left