各位题友大家好，今天是每日算法题公众号坚持日更的第 8 天。今天力扣上的每日一题是第 424 题「
替换后的最长重复字符」。可以通过每日一题的小程序查看题目详情：

题目大意

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

示例

**
输入：s = “AABABBA”, k = 1
输出：4
解释：
将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。
子串 “BBBB” 有最长重复字母, 答案为 4。

数据范围

注意：字符串长度 和 k 不会超过 10 ^ 4。

解题思路

首先需要区分两个概念：子串（子数组）和子序列。这两个名词经常在题目中出现，非常有必要加以区分。子串sub-string（子数组 sub-array）是连续的，而子序列 subsequence 可以不连续。

我读完今天这个题目之后，脑子里把题目转成了另外一个表达方式：求字符串中一个最长的区间，该区间内的出现次数较少的字符的个数不超过 k。**

上面的表达方式跟题目是等价的，抽象成这种表达方式的好处是让我们知道这是一个区间题，求子区间经常使用的方法就是双指针。

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

我分享一个双指针的模板，能解决大多数的双指针问题：

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

简单介绍上面的模板，模板的思想是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

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

模板中为什么不把 counter 放在 while 循环内部呢？因为如果放在 while 内部每次新建一个 counter 变量，统计区间的字符出现次数的时间复杂度是 O(N) ；放在 while 外部，每次增加 right 指向的字符的计数、减少 left 指向的字符的计数的是时间复杂度是 O(1) 。这也是常见的统计区间问题时的技巧。类似的，如果我们要求一个区间的和的话，也可以用类似的思想去做。

代码

今天的代码可以直接套用上面的双指针模板，内层的 while 循环中的判断条件该区间内出现次数较少的字符的出现次数是否大于 k 。如果大于 k 的话，说明该区间不符合题意，需要移动 left 指针直至符合题意为止。

如果理解了上面的双指针模板之后，我做了动图帮助理解。

424.gif

使用 Python2 写的代码如下。

  1. class Solution(object):
  2.     def characterReplacement(self, s, k):
  3.         """
  4.         :type s: str
  5.         :type k: int
  6.         :rtype: int
  7.         """
  8.         N = len(s)
  9.         left, right = 0, 0 # [left, right] 都包含
  10.         counter = collections.Counter()
  11.         res = 0
  12.         while right < N:
  13.             counter[s[right]] += 1
  14.             maxCnt = counter.most_common(1)[0][1]
  15.             while right - left + 1 - maxCnt > k:
  16.                 counter[s[left]] -= 1
  17.                 left += 1
  18.             res = max(res, right - left + 1)
  19.             right += 1
  20.         return res

刷题心得

欢迎加入刷题群

目前已经 2000 人加入了每日一题打卡群。加入方式是通过每日一题打卡网站。每天都会同步力扣每日一题，这是个互相帮助、互相监督的算法题打卡网站，其地址是 https://www.ojeveryday.com/
【每日一题】424. 替换后的最长重复字符 - 图2

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

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

关于作者

我是本文的作者是负雪明烛，毕业于北京邮电大学，目前就职于阿里巴巴。坚持刷算法题 5 年，共计刷了 800 多道算法题。做过的每个算法题都在 CSDN 上写题解博客，获得好评无数，CSDN 的累计阅读量已经 160万 次！博客地址是：
https://blog.csdn.net/fuxuemingzhu

「每日算法题」公众号是负雪明烛维护的一个算法题解公众号，主要讲解算法题的解法，也会分享找工作的经验。欢迎关注。
【每日一题】424. 替换后的最长重复字符 - 图3

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement