[LeetCode] 1208. Get Equal Substrings Within Budget

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)