LeetCode-424：替换后的最长重复字符

题目描述：

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

注意：字符串长度 和 k 不会超过 104。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
示例 2：

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

思路分析：

一看到最长字符串就想到滑动窗口。

算法流程：

• 右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
• 然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
• 替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
    public int characterReplacement(String s, int k) {
     
    
   

    

     

    
    

     
        int len=s.length();
     
    
   

    

     

    
    

     
        if(len<2){
     
    
   

    

     

    
    

     
            return len;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        char[] chararray=s.toCharArray();
     
    
   

    

     

    
    

     
        int left=0,right=0;
     
    
   

    

     

    
    

     
        int maxCount=0,res=0;
     
    
   

    

     

    
    

     
        int[] freq = new int[26];
     
    
   

    

     

    
    

     
        while(right<len){
     
    
   

    

     

    
    

     

                  freq[chararray[right]-'A']++;
     
    
   

    

     

    
    

     

                  maxCount=Math.max(maxCount,freq[chararray[right]-'A']);
     
    
   

    

     

    
    

     

                  right++;
     
    
   

    

     

    
    

     
            if(right-left>maxCount+k){
     
    
   

    

     

    
    

     

                      freq[chararray[left]-'A']--;
     
    
   

    

     

    
    

     

                      left++;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

                  res=Math.max(res,right-left);
     
    
   

    

     

    
    

     
            
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return res;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

复杂度分析：

时间复杂度：O(N)，这里 N 是输入字符串 S 的长度；
空间复杂度：O(A)，这里 A 是输入字符串 S 出现的字符 ASCII 值的范围。

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/113700187