今天和大家聊的问题叫做 替换后的最长重复字符，我们先来看题面：https://leetcode-cn.com/problems/reconstruct-original-digits-from-english/
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。注意：字符串长度 和 k 不会超过 10的4次方。
示例
示例 1： 输入：s = "ABAB", k = 2 输出：4 解释：用两个'A'替换为两个'B',反之亦然。 示例 2： 输入：s = "AABABBA", k = 1 输出：4 解释： 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。
解题
思路 ：由于题目是问最长子串，这种题目动态规划或者滑动窗口需要着重考虑一下，因为都是当前状态都是和之前相邻的状态有关。
1.先固定左边界，右边界一直右移，直到当前区间内的需要替换的字母数大于k。2.之后左边界右移，直到该区间需要替换的字母数小于等于k。重复1步骤。
问题是怎么找出某个区间内需要替换的字母数。
答案是用一个maxCnt数组记录各字母在当前区间内的出现次数，出现最多的，我们认为它就是主要字母，其他字母都替换为它。这样总的替换次数是最少的。
class Solution { public: int characterReplacement(string s, int k) { vector<int> counts(26, 0); //记录当前窗口字母出现的个数 int left=0, res=0, maxCnt=0; // maxCnt记录字符出现次数最多那个字符 的次数 for(int i=0; i<s.size(); i++){ counts[s[i]-'A']++; maxCnt = max(maxCnt, counts[s[i]-'A']); // 比较之前记录的最大数 和 当前字符的数量 while(i-left+1-maxCnt > k){ // 若当前窗口大小 减去 窗口中最多相同字符的个数 大于 k 时 counts[s[left]-'A']--; // 将窗口最左边的字符 在计数数组中减1 left++; // 滑动窗口 } res = max(res, i-left+1); } return res; } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
