Leetcode424-替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

题解

可以先做LCR 167/Leetcode 03再做本题

滑动窗口（截取字符串）+哈希表（快速获取窗口内每个字符的个数）

本题等价于替换窗口中的K个字符使其变成一个连续子串，我们的目的就是让窗口尽可能扩张，有K个字符的容错机会，容错机会肯定要用给map中出现次数最多的字符才有机会让窗口扩张 –>需要当前窗口中的出现次数最多的字母个数 +K >子串长度，此时当前窗口内的子串满足最长重复子串

算法步骤

一、定义参数： 变量maxOut记录窗口内最多字符的个度 变量res记录最长子字符串的长度 指针left记录滑动窗口的最左边界，初始值为0 指针right遍历数组，记录滑动窗口的最右边界 哈希表map记录窗口内每个字符的个数 chars = s.toCharArray()便于取值

二、遍历数组： 1.指针 right 遍历字符串s ，哈希表中添加chars[right]对应的字符次数 map[chars[right]-‘A’]++ 2.进行比较

如果maxOut<map[chars[right]-‘A’],更新maxOut如果maxOut+k>right-left+1,说明替换窗口中的K个字符可使其变成一个连续子串 (1)利用right-left+1更新res (2)否则的话，说明此时 k 不够用 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动 移出滑动窗口的时候，频数数组须要相应地做减法 map[chars[left]-‘A’]–; left++;

三、返回值： 返回res

class Solution { public int characterReplacement(String s, int k) { if (s == null) { return 0; } //利用数组代替哈希表，节约空间，本题只包含26个大写字母 int[] map = new int[26]; char[] chars = s.toCharArray(); int left = 0; int res = 0; int maxCount=0; for(int right=0;right<chars.length;right++){ int index=chars[right]-'A'; //窗口内s.charAt(right)出现的次数+1 map[index]++; // 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加 maxCount = Math.max(maxCount, map[index]); // 说明此时 k 不够用 // 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动 // 移出滑动窗口的时候，频数数组须要相应地做减法 if(maxCount+k < right-left+1){ map[chars[left]-'A']--; left++; }else{ res=Math.max(res,right-left+1); } } return res; } }