//brute force : O(n^2)
//ps : brute force is not giving TLE in leetcode submission :)

class Solution {
    public int characterReplacement(String s, int k) {
        //brute force approach :
        //getting all the substrings and finding out which can give the longest substring with repeating character
        int maxLen = 0;

        for(int i =0;i<s.length();i++){
            int arr[] = new int[26];
            int maxCount =0;
            for(int  j = i;j<s.length();j++){
                char c  = s.charAt(j);
                arr[c-'A']++;
                maxCount  = Integer.max(maxCount,arr[c-'A']);
                if(j-i+1 - maxCount <=k){
                    maxLen = Integer.max(maxLen, j-i+1);
                }
                else break; // else break out because the j-i+1-maxCount will always be greater than k in the current loop
            }
        }
        return maxLen;
    }
}

//O(2n) : o(n)for right pointer moving till the end of the String s length, O(n) for left pointer as in worst case left will also move till s.length()-2 index

class Solution {
    public int characterReplacement(String s, int k) {
        //two pointer sliding window protocol

        int left  =0;
        int right = 0;
        int arr[] = new int[26];
        int max = 0;
        int len  =0;
        while(right<s.length()){
            char c = s.charAt(right);
            arr[c-'A']++; //keep count of character in the array
            max  = Integer.max(max,arr[c-'A']); // get the max repeating character count
            while(right-left+1-max > k){ // if the no. of character to be replaced is more than allowed(k) then
// we will have to remove character 
//from left and decrement the character at index left by 1, and increment the left pointer by 1 to point to next 
//character i.e left+1
                arr[s.charAt(left)-'A']--;
                left++;
            }
            len  = Integer.max(len, right-left+1);
            right++;
        }
        return len;
    }
} 

//O(n) 

class Solution {
    public int characterReplacement(String s, int k) {
        //two pointer sliding window protocol

        int left  =0;
        int right = 0;
        int arr[] = new int[26];
        int max = 0;
        int len  =0;
        while(right<s.length()){
            char c = s.charAt(right);
            arr[c-'A']++;
            max  = Integer.max(max,arr[c-'A']);
            if(right-left+1-max > k){
                arr[s.charAt(left)-'A']--;
                left++;
            }
            len  = Integer.max(len, right-left+1);
            right++;
        }
        return len;
    }
}