各位题友大家好，今天是「每日算法题」公众号坚持日更的第 12 天。今天力扣上的每日一题是第 1208 题「尽可能使字符串相等」。可以通过每日一题的小程序查看题目详情：

题目描述

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

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

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

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

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

示例

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

数据范围

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

解题思路

今天这个题目比较难理解，我需要再解释一下。

两个长度相等字符串的 s 和 t ，把 i 位置的 s[i] 转成 t[i] 的开销是两者 ASCII 码之差的绝对值。题目给出了允许的最大预算 maxCost ，求不超过预算的情况下能够转换的最长子串。

比如，对于 s = "abcd", t = "bcdf", cost = 3 而言，我们使用 costs[i] 表示从 s[i] 转成 t[i] 的开销，那么 costs = [1, 1, 1, 2] 。由于 maxCost = 3， 所以最多允许其前面三个字符进行转换。

幻灯片1.JPG
于是题目变成了：已知一个数组 costs ，求：和不超过 maxCost 时最长的子数组的长度。

上面的表达方式跟题目是等价的。对题目抽象之后，是不是跟昨天的每日一题「643. 子数组最大平均数 I」非常像了？也和「424. 替换后的最长重复字符」非常像。这就是坚持刷每日一题的作用，大家继续坚持啊！

抽象之后，我们知道这是一个区间题，求子区间经常使用的方法就是滑动窗口。我在「424. 替换后的最长重复字符」的题解中已经分享了我珍藏的滑动窗口模板，由于模板是通用的，因此我把当时的题解再拿过来分享给大家。

《挑战程序设计竞赛》这本书中把滑动窗口叫做「虫取法」，我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动。

我分享一个滑动窗口的模板，能解决大多数的滑动窗口问题：

  1. def findSubArray(nums):
  2.     N = len(nums) # 数组/字符串长度
  3.     left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
  4.     sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
  5.     res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
  6.     while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
  7.         sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
  8.         while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
  9.             sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
  10.             left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
  11.         # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
  12.         res = max(res, right - left + 1) # 需要更新结果
  13.         right += 1 # 移动右指针，去探索新的区间
  14.     return res

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

  1. 定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；
  2. 第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的求和/计数；
  3. 第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的求和/计数；
  4. 在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。
  5. right 指针每次向右移动一步，开始探索新的区间。

模板中的 sums 需要根据题目意思具体去修改，本题是求和题目因此把sums 定义成整数用于求和；如果是计数题目，就需要改成字典用于计数。当左右指针发生变化的时候，都需要更新 sums 。

另外一个需要根据题目去修改的是内层 while 循环的判断条件，即： 区间[left, right]不符合题意 。对于本题而言，就是该区内的和 sums 超过了 maxCost 。

代码

我记住了上面的模板，在输入框里快速敲了一遍，直接点提交就通过了。

使用 Python2 写的代码如下。

  1. class Solution:
  2.     def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
  3.         N = len(s)
  4.         costs = [0]* N
  5.         for i in range(N):
  6.             costs[i] = abs(ord(s[i]) - ord(t[i]))
  7.         left, right = 0, 0
  8.         res = 0
  9.         sums = 0
  10.         while right < N:
  11.             sums += costs[right]
  12.             while sums > maxCost:
  13.                 sums -= costs[left]
  14.                 left += 1
  15.             res = max(res, right - left + 1)
  16.             right += 1
  17.         return res

时间复杂度： O(N) ，因为两个指针分别都只把每个元素遍历了一次。
空间复杂度： O(N) ，因为使用了 costs 数组用于保存每个字符转换的开销。

刷题心得

  1. 读了题目之后，要反应过来这是求一个最长区间的问题，从而想到滑动窗口。
  2. 滑动窗口是有模板的，理解之后，形成肌肉记忆，下次直接敲出来。
  3. 坚持刷每日一题，会发现自己在潜移默化中进步。

欢迎加入刷题群

目前已经近 2000 人加入了每日一题打卡群。加入方式是通过每日一题打卡网站。每天都会同步力扣每日一题，这是个互相帮助、互相监督的算法题打卡网站，其地址是 https://www.ojeveryday.com/
【每日一题】1208. 尽可能使字符串相等 - 图2

想加入千人刷题群的朋友，可以复制上面的链接到浏览器，然后在左侧点击「加入组织」，提交力扣个人主页，即可进入刷题群。期待你早日加入。

也可点击 「阅读原文」，直接提交力扣个人主页。

关于作者

我是本文的作者是负雪明烛，毕业于北京邮电大学，目前就职于阿里巴巴。坚持刷算法题 5 年，共计刷了 800 多道算法题。做过的每个算法题都在 CSDN 上写题解博客，获得好评无数，CSDN 的累计阅读量已经 160万 次！博客地址是：https://blog.csdn.net/fuxuemingzhu
「每日算法题」公众号是我维护的一个算法题解公众号，主要讲解算法题的解法，也会分享找工作的经验。欢迎关注。
【每日一题】1208. 尽可能使字符串相等 - 图3

题目来源：1208. 尽可能使字符串相等
链接：https://leetcode-cn.com/problems/get-equal-substrings-within-budget