340. Longest Substring with At Most K Distinct Characters

Link

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.

Solution

T: O(n), where n is s.length()

 public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int max = 0;
        int needToBeChanged = 0, mostFrequent = 0, left = 0;
        for(int right = 0; right < s.length(); right++ ){
            count[s.charAt(right) - 'A']++;
            mostFrequent = Math.max(mostFrequent, count[s.charAt(right) - 'A']);
            
            needToBeChanged = (right - left + 1) - mostFrequent;
            while(needToBeChanged > k){
                if(count[s.charAt(left)-'A'] == 1)
                    needToBeChanged--;
                count[s.charAt(left)-'A']--;
                left++;
            }
            
            max = Math.max(max, right-left+1);
        }
        return max;
    }