// Longest Repeating Character Replacement - https://leetcode.com/problems/longest-repeating-character-replacement/description/


class Solution {

    // Brute Force
    // Time Complexity: O(n^2)
    // Space Complexity: O(m) where m is number of letters in alphabet (26)
    // public int characterReplacement(String s, int k) {
    //     int maxLength = 0;

    //     for (int i = 0; i < s.length(); i++) {
    //         Map freq = new HashMap<>();
    //         int maxF = 0;
    //         for (int j = i; j < s.length(); j++) {
    //             char c = s.charAt(j);
    //             freq.put(c, freq.getOrDefault(c, 0) + 1);
    //             maxF = Math.max(maxF, freq.get(c));
                
    //             // len of current substring - count of most frequent character
    //             if((j - i + 1) - maxF <= k) {
    //                 maxLength = Math.max(maxLength, (j - i + 1));
    //             }
    //         }
    //     }

    //     return maxLength;
        
    // }

    // Sliding Window
    // Time Complexity: O(26.n) ~ O(n)
    // Space Complexity: O(26) ~ O(1)
    // public int characterReplacement(String s, int k) {
    //     int maxLength = 0;
    //     int l = 0;
    //     Map freq = new HashMap<>();
    //     for (int r = 0; r < s.length(); r++) {
    //         char c = s.charAt(r);
    //         freq.put(c, freq.getOrDefault(c, 0) + 1);
    //         int maxF = Collections.max(freq.values());
    //         int lenOfWindow = r - l + 1;
    //         if(lenOfWindow - maxF <= k) {
    //             maxLength = Math.max(maxLength, lenOfWindow);
    //         } else {
    //             while(lenOfWindow - maxF > k) {
    //                 char leftChar = s.charAt(l); 
    //                 freq.put(leftChar, freq.get(leftChar) - 1);
    //                 l++;
    //                 lenOfWindow--;
    //             }
    //         }
    //     }

    //     return maxLength;
    // }


    // Sliding Window (Optimised)
    // Time Complexity: O(n) 
    // Space Complexity: O(26) ~ O(1)
    public int characterReplacement(String s, int k) {
        int maxLength = 0;
        int l = 0;
        Map freq = new HashMap<>();
        int maxF = 0;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            freq.put(c, freq.getOrDefault(c, 0) + 1);
            maxF = Math.max(maxF, freq.get(c));

            while((r - l + 1) - maxF > k) {
                char leftChar = s.charAt(l); 
                freq.put(leftChar, freq.get(leftChar) - 1);
                l++;
            }
            maxLength = Math.max(maxLength, (r - l + 1));
        }

        return maxLength;
    }
}