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

🟠   🔖  哈希表 字符串 滑动窗口  🔗 力扣 LeetCode

题目

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2

Output: 4

Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1

Output: 4

Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".

The substring "BBBB" has the longest repeating letters, which is 4.

There may exists other ways to achieve this answer too.

Constraints:

• 1 <= s.length <= 10^5
• s consists of only uppercase English letters.
• 0 <= k <= s.length

题目大意

给你一个字符串 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^5
• s 仅由大写英文字母组成
• 0 <= k <= s.length

解题思路

1. 使用滑动窗口

   • 维护一个窗口 [left, right]，表示当前子串。
   • 计算窗口中出现最多的字符 maxFreq。
   • 计算窗口大小 (right - left + 1) 与 maxFreq 的差值，判断是否能通过 k 次替换使整个窗口变成相同字符。

2. 窗口扩展

   • 右指针 right 向右移动，记录字符出现频次，并更新 maxFreq。

3. 窗口收缩

   • 如果窗口大小 > maxFreq + k，表示需要替换的字符超过 k，因此左指针 left 右移收缩窗口。

4. 更新最大子串长度

   • 在窗口满足条件时，更新 res = max(res, right - left + 1)。

复杂度分析

• 时间复杂度：O(n)，右指针 right 线性扫描 s，每个字符最多被左指针 left 访问一次。
• 空间复杂度：O(1)，仅使用一个 Map 统计字符频次，最多 26 个英文字母。

代码

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function (s, k) {
	let count = new Map();
	let maxFreq = (res = left = 0);

	// 窗口扩展
	for (let right = 0; right < s.length; right++) {
		const char = s[right];
		const freq = (count.get(char) || 0) + 1;
		count.set(char, freq);

		// 计算窗口中出现最多的字符
		maxFreq = Math.max(freq, maxFreq);

		// 窗口收缩
		while (right - left + 1 - maxFreq > k) {
			count.set(s[left], count.get(s[left]) - 1);
			left++;
		}

		// 更新最大子串长度
		res = Math.max(res, right - left + 1);
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
340	至多包含 K 个不同字符的最长子串 🔒		哈希表 字符串 滑动窗口	🟠	🀄️ 🔗
1004	最大连续1的个数 III	[✓]	数组 二分查找 前缀和 1+	🟠	🀄️ 🔗
2009	使数组连续的最少操作数		数组 哈希表 二分查找 1+	🔴	🀄️ 🔗
2024	考试的最大困扰度		字符串 二分查找 前缀和 1+	🟠	🀄️ 🔗
2213	由单个字符重复的最长子字符串		线段树 数组 字符串 1+	🔴	🀄️ 🔗