You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.
You are also given an integer maxCost.
Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.
If there is no substring from s that can be changed to its corresponding substring from t, return 0.
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 charactor in `t, so the maximum length is 1.`
Example 3:
Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: You can't make any change, so the maximum length is 1.
Constraints:
1 <= s.length, t.length <= 10^50 <= maxCost <= 10^6sandtonly contain lower case English letters.
这道题给了两个字符串s和t，定义了一种 cost，是将 s[i] 变为 t[i] 的花费就是两个字母的 ASCII 码值的差的绝对值。现在给了一个最大花费额度 maxCost，问最多可以把s串的多少个连续字母转为t的对应字母，从而使得花费不超过给定的最大额度。这里强调了是s的子串，即中间不能有断开，若某个位置 s[i] 和 t[i] 相等，那最好了，花费为0，可以继续延长子串的长度。既然是子串，肯定是要连续的字母，那就一个一个的字母的累加，当花费超过给定值了，就将开头的字母去掉，从而减少总花费。这道 Medium 的题目其实主要就是考察滑动窗口 Sliding Window，维护一个特定长度的窗口，此时若窗口内的总花费小于给定值，则扩大窗口长度，即增加窗口的右边界。而一旦总花费超过给定值了，就要移除窗口最左边的元素，有时可能要连续移除多个，所以需要用一个 while 循环，条件是窗口内的总花费大于给定值，且左边界小于等于右边界，然后移除左边界的元素，并且左边界自增1。同时别忘了每次都用更新后的窗口长度来更新最终结果 res 即可，参见代码如下：
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int res = 0, n = s.size(), cur = 0, start = 0;
for (int i = 0; i < n; ++i) {
cur += abs(s[i] - t[i]);
while (cur > maxCost && start <= i) {
cur -= abs(s[start] - t[start]);
++start;
}
res = max(res, i - start + 1);
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1208
参考资料：
https://leetcode.com/problems/get-equal-substrings-within-budget/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
