#1208

Get Equal Substrings Within Budget

specialist · 725 · lc medium +31 · verified · 59.5% accepted · 1,919 likes · top 57%

Description

You are given two equal-length strings s and t and an integer maxCost.

Changing character s[i] to match t[i] costs |s[i] - t[i]| (absolute ASCII difference).

Find the maximum length of a contiguous substring of s that can be transformed into the corresponding portion of t with total cost at most maxCost. Return 0 if no such substring exists.

Example 1:

Input: s = "abcd", t = "bcdf", maxCost = 3

Output: 3

Explanation: "abc" of s can change to "bcd".

That costs 3, so the maximum length is 3.

Example 2:

Input: s = "abcd", t = "cdef", maxCost = 3

Output: 1

Explanation: Each character in s costs 2 to change to character in t, so the maximum length is 1.

Example 3:

Input: s = "abcd", t = "acde", maxCost = 0

Output: 1

Explanation: You cannot make any change, so the maximum length is 1.

Code

1

2

3

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int: