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

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

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

思路分析

解法一：滑动窗口（推荐）

核心思路：

用窗口统计字符频次，维护窗口内出现次数最多的字符 maxCount。

若窗口长度减去 maxCount 大于 k，说明需要替换的字符超限，移动左指针缩小窗口。

过程中维护最大窗口长度即为答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)，仅使用固定大小的计数数组。

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0;
        int maxCount = 0;
        int res = 0;

        for (int right = 0; right < s.length(); right++) {
            int idx = s.charAt(right) - 'A';
            count[idx]++;
            maxCount = Math.max(maxCount, count[idx]);

            while (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }

            res = Math.max(res, right - left + 1);
        }

        return res;
    }
}

func characterReplacement(s string, k int) int {
	count := make([]int, 26)
	left := 0
	maxCount := 0
	res := 0

	for right := 0; right < len(s); right++ {
		idx := s[right] - 'A'
		count[idx]++
		if count[idx] > maxCount {
			maxCount = count[idx]
		}

		for right-left+1-maxCount > k {
			count[s[left]-'A']--
			left++
		}

		if right-left+1 > res {
			res = right - left + 1
		}
	}

	return res
}

相似题目

题目	难度	考察点
3. 无重复字符的最长子串	中等	滑动窗口
1004. 最大连续1的个数 III	中等	滑动窗口
340. 至多包含 K 个不同字符的最长子串	困难	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口
159. 至多包含两个不同字符的最长子串	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/96513766