Longest Repeating Character Replacement

1package pkg5leetcode.blind75;2 3/*4 * Longest Repeating Character Replacement | LC 4245 * APPROACH: Sliding window; shrink when window - maxFreq > k.6 * COMPLEXITY: Time O(n), Space O(26)7 */8public class blind75_LC424LongestRepeatingCharacterReplacement {9    static int characterReplacement(String s, int k) {10        int[] count = new int[26];11        int left = 0, maxFreq = 0, best = 0;12        for (int right = 0; right < s.length(); right++) {13            maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);14            while (right - left + 1 - maxFreq > k) count[s.charAt(left++) - 'A']--;15            best = Math.max(best, right - left + 1);16        }17        return best;18    }19 20    public static void main(String[] args) {21        check(characterReplacement("ABAB", 2) == 4, "case1");22        check(characterReplacement("AABABBA", 1) == 4, "case2");23        System.out.println("all tests passed");24    }25 26    static void check(boolean cond, String name) {27        if (!cond) throw new AssertionError("FAILED: " + name);28        System.out.println("  PASS " + name);29    }30}