340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

重复character不能多余k个，于是可以维护一个window使得重复等于k个，当不满足要求的时候，移动左指针，知道满足要求。

与424. Longest Repeating Character Replacement 是一个思路

 public class Solution {  
   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;  
   }  
 }