424. Longest Repeating Character Replacement

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

简化问题：
目标是找一个最长的flip过的连续substring（每个character都相等）
给定k如果很大？或者k== length of string？
那么问题就成了找到如何花最小的cost（flip次数最少）flip可以弄成string里边全部一样？
   -找到maxCount（出现次数最多） 的character，然后把其他的flip成它
   minCost = length of string - maxCount

we can apply the at most k changes constraint

minCost  = length of string - maxCount <= k

在某处的时候我们的这个minCost会大于k，这个时候的substring不合法，我们要缩短这个substring使得minCost<=k
因此问题变成了维护一个window（连续substring），这个window满足constraint minCost  = length of string - maxCount <= k

count每一个character，维护maxCount来计算当前minCost。如果不满足constraints的时候，我们缩短window（move start pointer）这样length of string 会增加，maxCount可能减少

   public int characterReplacement(String s, int k) {  
     int start = 0;  
     int[] count = new int[26];  
     int maxCount = 0, ans = 0;  
     for(int end = 0; end < s.length(); end++){  
       char c = s.charAt(end);  
       count[c-'A']++;  
       if(count[c-'A'] > maxCount){  
         maxCount = count[c-'A'];  
       }  
       //minCost of substring to be all same characters = end - start + 1 - maxCount  
       //not satisfy constraint---not legal  
       while(end - start + 1 - maxCount > k){  
         count[s.charAt(start++)-'A']--;  
         //recompute maxCount  
         maxCount = 0;  
         for(int i = 0; i < 26; i++){  
           maxCount = Math.max(maxCount, count[i]);  
         }  
       }  
       ans = Math.max(ans,end-start+1);  
     }  
     return ans;  
   }  

DFS 超时。。。

 public class Solution {  
   Set<Character> dict = new HashSet<>();  
   int max = 0;  
   public int characterReplacement(String s, int k) {  
     if(s.length() == 0) return 0;  
     for(int i = 0; i < s.length(); i++)  
       dict.add(s.charAt(i));  
     dfs(s.toCharArray(),k,new HashSet<>());  
     return max;  
   }  
   public void dfs(char[] chars,int k,Set<Integer> visited){  
     int[] count = count(String.valueOf(chars));  
     max = Math.max(count[count.length-1],max);  
     if(k == 0)  
       return;  
     for(int i = 0; i < chars.length; i++){  
       if(visited.contains(i))  
         continue;  
       char tmp = chars[i];  
       for(char c: dict){  
         if(c==tmp )  
           continue;  
         chars[i] = c;  
         visited.add(i);  
         dfs(chars,k-1,visited);  
         visited.remove(i);  
       }  
       chars[i] = tmp;  
     }  
     return ;  
   }  
   public int[] count(String s){  
     int[] count = new int[s.length()+1];  
     count[0]=1;  
     count[s.length()-1]=1;  
     int max = 1;  
     for(int i = 1; i < s.length(); i++){  
       count[i] = s.charAt(i) != s.charAt(i-1)? 1:count[i-1] + 1;  
       max = Math.max(max,count[i]);  
     }  
     for(int i = s.length()-2; i >= 0; i--){  
       if(s.charAt(i) == s.charAt(i+1))  
         count[i] = count[i+1];  
     }  
     count[s.length()]=max;  
     return count;  
   }  
   public int[] copy(int[] nums){  
     int n = nums.length;  
     int[] copy = new int[n];  
     for(int i = 0; i < n; i++){  
       copy[i] = nums[i];  
     }  
     return copy;  
   }  
 }