LeetCode424：替换后的最长重复字符

题意

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

Solution1

枚举重复的字符，然后计算对应字符的能构成的最大长度，取最大值。

Code

class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length(), res = 0;
        for (int i = 0; i < 26; i++) {
            List<Integer> l = new ArrayList<Integer>();
            l.add(-1);
            for (int j = 0; j < n; j++) {
                if (s.charAt(j) - 'A' != i) {
                    l.add(j);
                }
            }
            if (l.size() <= k + 1) {
                res = n;
                break;
            }
            l.add(n);
            for (int j = k + 1; j < l.size(); j++) {
                res = Math.max(res, l.get(j) - l.get(j - k - 1) - 1);
            }
        }
        return res;
    }
}

Solution2

滑动窗口，一个区间满足条件的原则是$当前区间的长度<=区间内出现次数最多的字符 + k$，用滑动窗口维护即可。即当满足条件时，滑动窗口拓展，右端点++；不满足时，滑动窗口平移，左右端点++。滑动窗口的长度只会不断增大，遍历结束后滑动窗口的长度即为答案。

Code

class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length(), res = 0, l = 0, r = 0, ma = 0;
        int[] b = new int[26];
        for (r = 0; r < n; r++) {
            int now = s.charAt(r) - 'A';
            b[now]++;
            ma = Math.max(ma, b[now]);
            if (ma + k < r - l + 1) {
                b[s.charAt(l) - 'A']--;
                l++;
            }
        }
        return n - l;
    }
}