Longest Repeating Character Replacement

Problem Statement:

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. There may exists other ways to achieve this answer too.

Solution:

class Solution {
    public int characterReplacement(String s, int k) {
        int start = 0, end = 0, maxFreq = 0, ans = 0;
        int[] charCount = new int[26]; // Array to store counts of each character
 
        while (end < s.length()) {
            charCount[s.charAt(end) - 'A']++; // Include the current character in the window
            // Update the maximum frequency of any character in the current window
            maxFreq = Math.max(maxFreq, charCount[s.charAt(end) - 'A']); 
            
 
            int windowSize = end - start + 1;
            int charsToReplace = windowSize - maxFreq;
 
            // Check if the current window can be made uniform by replacing at most 'k' characters
            if (charsToReplace <= k) {
                ans = Math.max(ans, windowSize); // Update the answer with the current window size
            } else {
                charCount[s.charAt(start) - 'A']--; // Remove the character at 'start'
                start++; // Shrink the window from the start
            }
 
            end++; // Expand the window by moving the end pointer
        }
 
        return ans; // Return the length of the longest substring
    }
}