1208. Get Equal Substrings Within Budget

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^5
  • 0 <= maxCost <= 10^6
  • s and t only 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/

https://leetcode.com/problems/get-equal-substrings-within-budget/discuss/392837/JavaC%2B%2BPython-Sliding-Window

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation