20. Longest Repeating Character Replacement

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.

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.

Solution: (Sliding Window)

Approach: We need to maintain a window such that (start - end - maxCharCount <=k) and find the max len possible window

class Solution
{
public:
    int characterReplacement(string s, int k)
    {

        int start = 0;
        int end = 0;
        int maxLen = 0;

        vector<int> count(26, 0);

        int maxCount = 0;

        while (end < s.length())
        {

            count[s[end] - 65]++;

            if (count[s[end] - 65] > maxCount)
            {
                maxCount = count[s[end] - 65];
            }

            end++;

            while (end - start - maxCount > k)
            {
                maxCount = 0;
                count[s[start] - 65]--;
                start++;

                for (int i = 0; i < 26; i++)
                {
                    if (count[i] > maxCount)
                    {
                        maxCount = count[i];
                    }
                }
            }

            maxLen = max(maxLen, end - start);
        }

        return maxLen;
    }
};