LC #424

class Solution {
    public int characterReplacement(String s, int k) {

        //map to keep track of elements in the window
        //Keep highest frequency character
        HashMap<Character, Integer> dict = new HashMap<>();
        int bestFreq = 0;

        //longest length answer to return <- longest valid window (subarray)
        int ans = 0;

        //back window pointer
        int back = 0;

        for (int front=0; front<s.length(); front++) {
            //window increment
            char c = s.charAt(front);
            //increment frequency
            dict.put(c, dict.getOrDefault(c, 0) + 1);

            int freq = dict.get(c);
            //check for best frequency, this is because the only way to maximize score is
            //having a large window size with a large frequency of recurring characters, therefor
            //having a low amount of characters to swap K times
            // bestFreq = freq > bestFreq ? freq : bestFreq;
            bestFreq = Math.max(bestFreq, freq);

            //check window validity
            int windowsize = front - back + 1;
            while (windowsize - bestFreq > k) {
                //invalid window, too many characters require replacement but not enough Ks
                //shrink so that the window is valid within k replacelemt constraint
                //remove character at back
                dict.put(s.charAt(back), dict.get(s.charAt(back)) - 1);
                back++;
                //update the window size
                windowsize = front - back + 1;

            }
            //valid window, check if it is the better solution
            // ans = windowsize > ans ? windowsize : ans;
            ans = Math.max(ans, windowsize);
        }
        return ans;
    }
}