1208. Get Equal Substrings Within Budget

题目信息

题号:

1208

难度:

Medium

主题:

字符串、滑动窗口、连续子串、成本限制

原题:

LeetCode 1208

重点:

选择两个字符串中相同下标范围的连续子串;把 s[i] 改为 t[i] 的成本为字符编码差的绝对值

题目重述

给定长度相同的小写字符串 s 和 t,以及预算 maxCost。把位置 i 的字符从 s[i] 改成 t[i] 需要花费 |s[i] - t[i]|,其中字母按英文字母顺序编号。

选择一个连续下标区间,并把该区间内 s 的字符全部改成 t 对应字符。请返回总成本不超过预算时能够选择的最长区间长度;允许选择空区间。

1 <= s.length == t.length <= 10^5,两个字符串只包含小写英文字母,0 <= maxCost <= 10^6。

自建示例

预算只够覆盖一个高成本位置:

输入:s = "abcd", t = "abxy", maxCost = 21
输出:3
解释:区间 [0,2] 的成本为 0 + 0 + 21 = 21,长度为 3;包含最后两个高成本位置的更长区间会超出预算。

零预算仍可选择完全相同的整段:

输入:s = "same", t = "same", maxCost = 0
输出:4
解释:每个位置的转换成本都为 0,因此整个字符串都可选择。