424 longest repeating character replacement

https://leetcode.com/problems/longest-repeating-character-replacement/

马甲题，其实就是控制string里面不同的字符不要超过k个的最长substring

这里的思路类似于395

class Solution {
    public int characterReplacement(String s, int k) {
        char[] input = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int ans = 0;
        int n = input.length;
        for (char ch : input) {
            set.add(ch);
        }
        for (char curCh : set) {
            // char curCh = (char)('A' + i);
            int l = 0;
            int diffCnt = 0;
            for (int r = 0; r < n; r++) {
                if (curCh != input[r]) {
                    diffCnt++;
                } 
                while (diffCnt > k) {
                    if (curCh != input[l]) {
                        diffCnt--;
                    }
                    l++;
                }
                ans = Math.max(ans, r - l + 1);
            }
        }
        return ans;
    }
}

你也可以反转一下，这样就不用针对每个char单独查一次了。在每个range里以重复次数最多的char为基础（maxsame），然后要求除此之外的char不能超过k个。

class Solution {
    public int characterReplacement(String s, int k) {
        char[] arr = s.toCharArray();
        int[] freqs = new int[26];
        int maxSame = 0;
        int i = 0;
        int maxLen = 0;
        for (int j = 0; j < arr.length; j++) {
            char ch = arr[j];
            freqs[ch-'A']++;
            maxSame = Math.max(maxSame, freqs[ch-'A']);
            while (j-i+1-maxSame > k) {
                ch = arr[i++];
                freqs[ch-'A']--;
                if (freqs[ch-'A'] == 0) {
                    maxSame = Math.max(maxSame, freqs[ch-'A']);
                }
            }
            maxLen = Math.max(maxLen, j-i+1);
        }
        return maxLen;
    }
}