原文链接: https://leetcode-cn.com/problems/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。

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

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

输入：s = "abcd", t = "acde", maxCost = 0
输出：1
解释：a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。

 

提示：

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

通过代码

高赞题解

最终更新

经过与官方的一些讨论，目前将计算过程仅与「两端点」相关的称为「双指针」，将计算过程与「两端点表示的区间」相关的称为「滑动窗口」。

下文定义与此不同，仅供参考。

前言

相信各位 Leetcoder 通过 2 月份前几天的打卡题，已经大概猜测出这个月的打卡题都是与「滑动窗口」和「双指针」相关的。然而我鲜有看见有人尝试去说一说这二者的区别的，并且在这几天打卡题的题解区里，有不少将这两个名词混用的现象。

如果「滑动窗口」和「双指针」没有啥区别，可以互相替换，那么我们显然不会为一个笔试和面试中常考的知识点进行冗余的命名。一些没有命中要害的文章可能是这样分析的：

• 「滑动窗口」是固定大小的，「双指针」是不固定大小的；

• 「滑动窗口」一定是同向移动的，「双指针」可以相向移动。

而本篇文章会直接命中要害，说一说二者的区别。

滑动窗口

如果对 TCP 有一定了解的同学，会知道「滑动窗口」这个概念就来源于 TCP 中的一个传输协议。维基百科中的 Sliding window protocol 告诉我们：

The transmitter and receiver each have a current sequence number $n_t$ and $n_r$, respectively. They each also have a window size $w_t$ and $w_r$. The window sizes may vary, but in simpler implementations they are fixed. The window size must be greater than zero for any progress to be made.

也就是说，「滑动窗口」本身是可以固定或者不固定大小的。我们再来看看 Windows 中对此的设计，参考维基百科中的 TCP window scale option：

TCP Window Scaling is implemented in Windows since Windows 2000. It is enabled by default in Windows Vista / Server 2008 and newer, but can be turned off manually if required. Windows Vista and Windows 7 have a fixed default TCP receive buffer of 64 kB, scaling up to 16 MB through “autotuning”, limiting manual TCP tuning over long fat networks.

也就是说，「滑动窗口」是一个默认固定大小的窗口，在一些条件触发的情况下，可能会将其大小进行修改。

了解了「滑动窗口」的概念后，我们再来看看 Leetcode 上都有哪些「滑动窗口」的题目。我们直接搜索「滑动窗口」这一关键词（而不是「滑动窗口」这一标签），可以得到下面的这些题目：

• 239. 滑动窗口最大值

• 346. 数据流中的移动平均值

• 480. 滑动窗口中位数

这些题目都可以抽象成如下的一个模型：

给定一个长度为 $n$ 的数组 $A$，我们需要进行 $q$ 次询问，每次询问的是数组中的一个连续的子数组 $A[l .. r]$，希望获取该子数组的一些相关信息。如果第 $i$ 个询问的子数组的左端点为 $l_i$，那么必须满足 $l_i \leq l_{i+1}$，即窗口是在向某一个方向（例如向右）进行滑动的。而不同的 $r_i$ 之间不需要存在联系，即窗口是可以变长的。

因此，「滑动窗口」本身并不是解决问题的一种方法（或者说算法），它其实就是这个问题本身。我们需要做的是寻找合适的数据结构来「维护」这个「滑动窗口」。例如：

• 在 239. 滑动窗口最大值 中，我们使用单调队列进行维护；

• 在 480. 滑动窗口中位数 中，我们使用两个优先队列 / 两棵平衡树 / 一棵平衡树进行维护。

这样「滑动窗口」的概念就非常清晰了。

双指针

「双指针」是什么？如果理解了「滑动窗口」，那么「双指针」与其一个非常明显的区别就是：「双指针」不会成为这个问题本身，而是解决问题的一种方法。

那么「双指针」可以用来解决什么问题呢？我们首先想一想两个同向移动的指针在解决什么问题，就以今天的打卡题 1208. 尽可能使字符串相等，抽象出一个模型：

给定一个长度为 $n$ 的数组 $A$，我们需要找出其中一个最长（或者短）的连续子数组，满足题目中给定的要求。

常用的基于「双指针」的解决办法是：我们可以枚举子数组的左边界 $l$，随后尝试向右扩展右边界 $r$，使得 $A[l .. r]$ 满足（或者不满足）要求但是 $A[l .. r+1]$ 不满足（或者满足）。此时一个极大（或者小）的满足要求的区间就是 $A[l .. r]$，最终所有极大（或者小）区间的最大（或者小）长度就是所要求出的答案。

那么这里就有两个重点中的重点，也就是「双指针」这一方法正确性的必要条件：

• 对于左边界 $l_i$ 而言，如果极大的区间对应的右边界为 $r_i$，那么
  $$
  A[l_i .. l_i], A[l_i .. l_{i+1}], \cdots, A[l_i .. r_i]
  $$
  这些区间都是满足要求的，而
  $$
  A[l_i .. r_i+1], \cdots, A[l_i .. n-1]
  $$
  这些区间都是不满足要求的。因此：

  $r_i$ 就是关于 $l_i$ 的最大的满足要求的右边界，并且在 $r_i$ 左侧都满足要求，在 $r_i$ 右侧都不满足要求。

  这个问题实际上是可以用「二分查找」来解决的：如果我们将「满足要求」看成 $0$，「不满足要求」看成 $1$，那么我们就是在一个只包含 $0/1$ 并且升序的序列中查找最后出现的那个 $0$，这就是最简单的「二分查找」问题了。

• 对于右边界 $r_i$ 而言，它具有单调性，也就是 $r_i \leq r_{i+1}$，否则我们不可能使用另一个指针维护右边界。如果 $r_i$ 没有单调性，我们就可以简单地使用「二分查找」来进行解决，而一旦 $r_i$ 有了单调性，那么我们就可以省去二分查找，直接使用一个指针维护右边界，优化掉一个 $\log$ 的时间复杂度。

这样我们就理解了双指针在同向移动的指针时的本质。而如果双指针是相向移动的，例如 167. 两数之和 II - 输入有序数组，我们可以将原数组复制一份并且进行反转，记为 $B$，那么原先的两个指针在数组 $A$ 上相向移动，就等价于两个指针分别在数组 $A$ 和 $B$ 上同向移动，那么这两种情况就是一致的了。

补充

可能有些读者会觉得上面的阐述和例子不太好理解，这里补充再说一些。

• 第一是考虑 239. 滑动窗口最大值 这个问题，是无法使用双指针来解决的，所以同向移动的双指针和滑动窗口没有任何联系，只是它们碰巧长得比较像而已，不要望文生义。

• 第二是考虑例如「打家劫舍问题」「股票问题」「跳跃游戏问题」之类的经典问题类型，可以发现「滑动窗口」和这些类型是类似的，所以「滑动窗口」是一类问题，其中不同的问题需要使用不同的算法和数据结构来解决。

总结

很简单，就两句话。

「滑动窗口」是一类问题本身，「双指针」是解决一类二分查找问题的通用优化方法。
二者关联的问题之间没有任何关系。

统计信息

通过次数	提交次数	AC比率
49533	99599	49.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言