1208. Get Equal Substrings Within Budget

meat two_pointer prefix_sum 同向双指针 模板

Q: 给定两个同等长度的字符串, 两个字符串之间的距离就是更改他们的成本,
i.e. c -> a, cost = ord("c") - ord("a") = 2
让你计算在指定成本 max_cost 范围内, 尽可能多的修改字符, 求能得到的最长子串长度.

思路: 先初始化一个差值绝对值的前缀和数组,
然后用同向双指针模板, (循环)固定每一个右指针, 直到越过指定成本:
内循环, 递增左指针, 找左右指针能够扩展的最长距离.

O(n) time.

while r < n:
    r += 1
    while pre_sum[r] - pre_sum[l] > maxCost # and l <= r:
        l += 1
    if r - l > max_len:
        max_len = r - l
return max_len

<code>
class Solution:
    def equalSubstring(self, s, t, maxCost):
        n = len(s)
        pre_sum = [0]
        for i in range(n):
            cost = abs(ord(t[i]) - ord(s[i]))
            pre_sum.append(pre_sum[-1] + cost)
        l, r = 0, 0
        max_len = 0
        while r < n:
            r += 1
            while pre_sum[r] - pre_sum[l] > maxCost:
                l += 1
            if r - l > max_len:
                max_len = r - l
        return max_len

o = Solution()
s = "krrgw"
t = "zjxss"
maxCost = 19
ans = o.equalSubstring(s, t, maxCost)
print(ans)