题目描述

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销，也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。

将 s 的子字符串部分转化为它在 t 中对应的子字符串满足总开销应当小于等于 maxCost，返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

样例

输入：s = "abcd", t = "bcdf", cost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。

输入：s = "abcd", t = "cdef", cost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

输入：s = "abcd", t = "acde", cost = 0
输出：1
解释：你无法作出任何改动，所以最大长度为 1。

限制

• 1 <= s.length, t.length <= 10^5
• 0 <= maxCost <= 10^6
• s 和 t 都只含小写英文字母。

算法

(滑动窗口，双指针) $O(n)$

1. 我们维护一个当前可行的窗口 [j, i]，每次将 i 尝试向后一格，如果开销过大，则将 j 也向后移动，直到开销小于等于 maxCost 为止。
2. 也就是说，对于每次 i 的移动，维护 j 的位置，然后统计答案。

时间复杂度

• 每个位置仅遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 只需要常数的额外变量，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.length();
        int cur = 0, len = 0;
        for (int i = 0, j = 0; i < n; i++) {
            cur += abs(s[i] - t[i]);
            while (cur > maxCost) {
                cur -= abs(s[j] - t[j]);
                j++;
            }
            len = max(len, i - j + 1);
        }

        return len;
    }
};