package Leetcode.SlideWindow;

/**
 * @author zhengstars
 * @date 2024/03/27
 */
public class LongestRepeatingCharacterReplacement {

    // Main function to calculate the longest repeating character with replacement
    public static int characterReplacement(String s, int k) {
        // Convert the input string to character array
        char[] cur = s.toCharArray();

        // Declare an array to store counts of each letter
        int[] map = new int[26];
        // Get the length of the input string
        int n = s.length();
        // Initialize the max length
        int ans = 0;
        // Initialize the left pointer of the sliding window
        int left = 0;

        // Start sliding window from the left to the right
        for (int right = 0; right < n; right++) {
            // Calculate the index of current character in the map array
            int rider = cur[right] - 'A';
            // Increase the count of current character
            map[rider]++;
            // Update the max count
            ans = Math.max(ans, map[rider]);

            // If the length of the current window minus max count is larger than k
            if (right - left + 1 > ans + k) {
                // Decrease the count of the character at left pointer
                map[cur[left] - 'A']--;
                // Move the left pointer to the right by one unit
                left++;
            }
        }
        // Return the max length of the substring
        return cur.length - left;
    }

    public static void main(String[] args) {
        // Test case 1
        String s1 = "ABAB";
        int k1 = 2;
        // Print the result of the test case 1
        System.out.println(characterReplacement(s1, k1));

        // Test case 2
        String s2 = "AABABBA";
        int k2 = 2;
        // Print the result of the test case 2
        System.out.println(characterReplacement(s2, k2));
    }
}