尽可能使字符串相等（1208）

题目

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

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

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 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 都只含小写英文字母。

算法

数组

使用数组cost保存每个位置的开销，然后我们在数组cost中寻找连续的位置满足这些位置的值的和满足最大开销，最后返回这些连续位置的长度即可

export const equalSubstring = (s, t, maxCost) => {
	let i = 0,
		j = 0;
	const cost = [];
	while (i < s.length && j < t.length) {
		cost[i] = Math.abs(s[i].charCodeAt() - t[j].charCodeAt());
		i++;
		j++;
	}
	let res = 0;
	for (let m = 0; m < cost.length; m++) {
		let max = 0;
		let residue = maxCost;
		for (let n = m; n < cost.length; n++) {
			if (cost[n] <= residue) {
				max++;
				residue -= cost[n];
			} else {
				break;
			}
		}
		res = Math.max(res, max);
	}
	return res;
};

滑动窗口

我们使用左指针left和右指针right来维护一个滑动窗口，使用curCost变量来保存当前的开销

• 当右指针right对应位置的开销Math.abs(s[right]-t(right))加上已经花费的开销curCost仍小于最大开销maxCost时，说明当前窗口对应的s可以变换后等于t的子串，我们用两个指针left和right已经记录当前最大窗口长度，我们将right对应位置的开销加到curCost中
• 当右指针right对应位置的开销加上已经花费的开销大于最大开销时，说明此时的子串不满足条件，我们同时移动向右移动指针left和right，在curCost中加入右指针的开销、减去左指针的开销

最后返回的结果就是两个指针保存的最大窗口长度right-left

export const equalSubstring = (s, t, maxCost) => {
	let left = 0,
		right = 0;
	let curCost = 0;
	while (right < s.length && right < t.length) {
		const cost = Math.abs(s[right].charCodeAt() - t[right].charCodeAt());
		if (cost + curCost > maxCost) {
			curCost -= Math.abs(s[left].charCodeAt() - t[left].charCodeAt());
			left++;
		}
		curCost += cost;
		right++;
	}
	return right - left;
};