本文共 1036 字，大约阅读时间需要 3 分钟。

双指针法是解决这个问题的高效方法。通过维护一个区间[j, i]，并用count数组记录区间内每个字母的出现次数。当区间内的字符总数减去出现次数最多的字母的出现次数大于k时，右移左指针j，直到满足条件。每次满足条件时，更新最长子串的长度。

思路解析

• 双指针维护区间：使用左右两个指针j和i来确定当前的区间[j, i]。j从左向右移动，i从左向右扩展。
• 记录字母出现次数：使用count数组记录区间内每个字母的出现次数。
• 检查条件：当区间内的总字符数减去出现次数最多的字母的次数大于k时，右移j，直到满足条件。
• 更新最长子串长度：每次满足条件时，计算区间长度并更新最大值。

代码解析

public class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int res = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'A']++;
            while (!check(count, k)) {
                count[s.charAt(j) - 'A']--;
                j++;
            }
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
    private boolean check(int[] count, int k) {
        int sum = 0, max = 0;
        for (int i : count) {
            sum += i;
            max = Math.max(max, i);
        }
        return sum - max <= k;
    }
}

时间复杂度

• O(n)：每个字符只被处理一次，时间复杂度为O(n)。
• 空间复杂度：使用了一个固定大小的数组count，空间复杂度为O(1)。

这个方法高效且简洁，能够在O(n)的时间内解决问题，适用于长字符串。

转载地址：http://xkjs.baihongyu.com/