424. 替换后的最长重复字符

题目描述

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
可能存在其他的方法来得到同样的结果。

提示：

1 <= s.length <= 10⁵
s 仅由大写英文字母组成
0 <= k <= s.length

解法

方法一：双指针

我们使用一个哈希表 cnt 统计字符串中每个字符出现的次数，使用双指针 l 和 r 维护一个滑动窗口，使得窗口的大小减去出现次数最多的字符的次数，结果不超过 $k$。

我们遍历字符串，每次更新窗口的右边界 r，并更新窗口内的字符出现次数，同时更新出现过的字符的最大出现次数 mx。当窗口的大小减去 mx 大于 $k$ 时，我们需要缩小窗口的左边界 l，同时更新窗口内的字符出现次数，直到窗口的大小减去 mx 不大于 $k$。

最后，答案为 $n - l$，其中 $n$ 为字符串的长度。

Python3JavaC++GoTypeScript

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = Counter()
        l = mx = 0
        for r, c in enumerate(s):
            cnt[c] += 1
            mx = max(mx, cnt[c])
            if r - l + 1 - mx > k:
                cnt[s[l]] -= 1
                l += 1
        return len(s) - l

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

class Solution {
public:
    int characterReplacement(string s, int k) {
        int cnt[26]{};
        int l = 0, mx = 0;
        int n = s.length();
        for (int r = 0; r < n; ++r) {
            mx = max(mx, ++cnt[s[r] - 'A']);
            if (r - l + 1 - mx > k) {
                --cnt[s[l++] - 'A'];
            }
        }
        return n - l;
    }
};

func characterReplacement(s string, k int) int {
    cnt := [26]int{}
    l, mx := 0, 0
    for r, c := range s {
        cnt[c-'A']++
        mx = max(mx, cnt[c-'A'])
        if r-l+1-mx > k {
            cnt[s[l]-'A']--
            l++
        }
    }
    return len(s) - l
}

function characterReplacement(s: string, k: number): number {
    const idx = (c: string) => c.charCodeAt(0) - 65;
    const cnt: number[] = Array(26).fill(0);
    const n = s.length;
    let [l, mx] = [0, 0];
    for (let r = 0; r < n; ++r) {
        mx = Math.max(mx, ++cnt[idx(s[r])]);
        if (r - l + 1 - mx > k) {
            --cnt[idx(s[l++])];
        }
    }
    return n - l;
}

424. 替换后的最长重复字符

题目描述

解法

方法一：双指针

评论