1208. Get Equal Substrings Within Budget¶
题目信息¶
- 题号:
1208
- 难度:
Medium
- 主题:
字符串、滑动窗口、连续子串、成本限制
- 原题:
- 重点:
选择两个字符串中相同下标范围的连续子串;把
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,因此整个字符串都可选择。