You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

&nbsp;
Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.


Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s consists of only uppercase English letters.
	0 &lt;= k &lt;= s.length


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # Initialize variables
        window_start = 0
        max_length = 0
        max_count = 0
        char_count = {}

        # Traverse the string s
        for window_end in range(len(s)):
            # Increment the count of the current character
            char_count[s[window_end]] = char_count.get(s[window_end], 0) + 1
            # Update the maximum count seen so far
            max_count = max(max_count, char_count[s[window_end]])
            
            # Shrink the window if required
            if window_end - window_start + 1 > max_count + k:
                char_count[s[window_start]] -= 1
                window_start += 1
            
            # Update the maximum length of the substring with repeating characters seen so far
            max_length = max(max_length, window_end - window_start + 1)
        
        return max_length
class Solution {
    public int characterReplacement(String s, int k) {
        HashMap<Character,Integer> map=new HashMap<>();
            int i=-1;
            int j=-1;
            int ans=0;
            while(true){
            boolean f1=false;
            boolean f2=false;
            while(i<s.length()-1){
                //acquire
               i++;
               f1=true;
               char ch=s.charAt(i);
               map.put(ch,map.getOrDefault(ch,0)+1);
               int count=0;
               for(char key:map.keySet()){
                   count=Math.max(count,map.get(key));
               }
               int replace=(i-j) - count;
               if(replace<=k) {
                   ans=Math.max(i-j,ans);
               } 
               else break;
                   
             }
                
             while(j<i){
               //release   
               f2=true;  
               j++;
               char ch=s.charAt(j);
               isremove(map,ch);
               int count=0;
               for(char key:map.keySet()){
                   count=Math.max(count,map.get(key));
               }
               int replace=(i-j) - count;  
               if(replace<=k){
                   ans=Math.max(i-j,ans);
                   break;
               }
               else continue;  
             }   
             if(f1==false && f2==false) break;   
                
         }
        
        return ans;
    }
    
    
    static void isremove(HashMap<Character,Integer> map,char ch){
        if(map.get(ch)==1) map.remove(ch);
        else map.put(ch,map.get(ch)-1);
    }
}
class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.length();
        if(n == k) return n;
        if(n == 1) return 1;

        int res = 0;
        int maxCnt = 0;
        
        unordered_map<char,int> mp;
        
        for(int l = 0, r = 0; r < n; r++)
        {
            mp[s[r]]++;
            maxCnt = max(maxCnt,mp[s[r]]);
            while(r - l + 1 - maxCnt > k){
                mp[s[l]]--;
                l++;
            }
            res = max(r - l + 1, res);
        }
        return res;
    }
};
// O(n) time | O(26) -> O(1) space - only uppercase English letters
var characterReplacement = function(s, k) {
    const sLen = s.length, 
          charCount = {};
    if (k >= sLen) return sLen;
    let maxLen = 0,
        windowStart = 0,
        maxRepeatChar = 0;
    for (let windowEnd = 0; windowEnd < sLen; windowEnd++) {
        // increment charCount
        charCount[s[windowEnd]] ? charCount[s[windowEnd]]++ : charCount[s[windowEnd]] = 1;
        // calc max repeating char
        maxRepeatChar = Math.max(maxRepeatChar, charCount[s[windowEnd]]);
        // calc number of char that is not (or has fewer chars) repeating in window
        const remainingChar = windowEnd - windowStart + 1 - maxRepeatChar;
        // slide window by incrementing start of window
        if (remainingChar > k) {
            // decrement charCount
            charCount[s[windowStart]]--;
            windowStart++;
        }
        // calc maxLen
        maxLen = Math.max(maxLen, windowEnd - windowStart + 1);
    }
    return maxLen;
};
Longest Repeating Character Replacement