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

<p>Return <em>the length of the longest substring containing the same letter you can get after performing the above operations</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ABAB&quot;, k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> Replace the two &#39;A&#39;s with two &#39;B&#39;s or vice versa.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;AABABBA&quot;, k = 1
<strong>Output:</strong> 4
<strong>Explanation:</strong> Replace the one &#39;A&#39; in the middle with &#39;B&#39; and form &quot;AABBBBA&quot;.
The substring &quot;BBBB&quot; has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of only uppercase English letters.</li>
	<li><code>0 &lt;= k &lt;= s.length</code></li>
</ul>

#include <iostream>
#include <unordered_map>
#include <map>
using namespace std;
class Solution {
public:
    int characterReplacement(string s, int k) {
        
        //(window_size)-(max_freq) => no of replacements
        //no of replacements <= k

        // int l=0,r=0;
        // int winSize=r-l+1;
        // int n=s.size();
        // int max_count=0;
        // vector<int> count(26,0);
        // while(r<n)
        // {
        //     while(winSize-max_count <= k && r<n)
        //     {
        //         winSize=r-l+1;
        //         count[s[r]]++;
        //         r++;
        //         max_count=*max_element(count.begin(),count.end());
        //     }
        //     count[s[l]]--;
        //     l++;
        // }
        // return winSize;


        // int l=0,r=0;
        // int n=s.size();
        // int max_count=0;
        // int res=0,maxf=0;
        // while(r<n)
        // {
        //     hashmap[s[r]]++;
        //     maxf=max(maxf,hashmap[s[r]]);
        //     if((r-l+1)-maxf > k)
        //     {
        //         hashmap[s[l]]--;
        //         l++;
        //         // max_count=(*mpd::max_element(hashmap.begin(), hashmap.end())).second;
        //     }
        //     else
        //         res=max(res,r-l+1);
        //     r++;
        // }
        // return res;

        // int n=s.size();
        // int l=0,r=0;
        // unordered_map<char> mp;
        // int count=0;
        // int maxi=0;
        // int t=0;
        // while(r<n)
        // {
        //     if(mp.find(s[r]) == mp.end())
        //     {
        //         mp.insert(s[r]);
        //     }
        //     count=r-l+1;
        //     maxi=max(maxi,count);
        //     while()
        //     r++;
        // }
        // return maxi;

        unordered_map<char,int> mp;
        int l=0,r=0;
        int n=s.size();
        int max_freq=0;
        int window_size=0;
        int maxLen=0;
        while(r<n)
        {
            mp[s[r]]++;
            max_freq=max(max_freq,mp[s[r]]);
            window_size=r-l+1;
            while(window_size - max_freq > k && l<=r)
            {
                mp[s[l]]--;
                l++;
                window_size=r-l+1;
                max_freq=0;
                for(int i=0;i<mp.size();i++)
                    max_freq=max(max_freq,mp[i]);
            }

            if(window_size - max_freq <= k)
            {
                maxLen=max(maxLen,window_size);
            }
            r++;
        }
        return maxLen;

        // unordered_map<char, int> mp;
        // int l = 0, r = 0;
        // int n = s.size();
        // int max_freq = 0; // Track the highest frequency of any character in the current window
        // int maxLen = 0;

        // while (r < n) {
        //     // Increase the count for the current character
        //     mp[s[r]]++;
        //     // Update max_freq with the highest frequency in the current window
        //     max_freq = max(max_freq, mp[s[r]]);

        //     // Calculate the size of the current window
        //     int window_size = r - l + 1;

        //     // If the window has more than k characters that need to be replaced, shrink it
        //     if (window_size - max_freq > k) {
        //         mp[s[l]]--; // Remove the leftmost character from the window
        //         l++;        // Move the left boundary to the right
        //     }

        //     // Update maxLen with the size of the current valid window
        //     maxLen = max(maxLen, r - l + 1);
        //     r++;
        // }

        // return maxLen;
    }
};
9900