LeetCode 424: Longest Repeating Character Replacement (Sliding Window + Max Frequency)
LeetCode 424StringSliding WindowToday we solve LeetCode 424 - Longest Repeating Character Replacement.
Source: https://leetcode.com/problems/longest-repeating-character-replacement/
English
Problem Summary
Given an uppercase string s and integer k, you can replace at most k characters in a substring so all characters become the same. Return the maximum possible substring length.
Key Insight
For a window [l..r], let maxFreq be the highest frequency of one character in this window. The minimum replacements needed is windowLen - maxFreq. The window is valid if this value is <= k.
Brute Force and Limitations
Brute force checks all substrings and computes the most frequent character each time, which is O(n^2 * alphabet). Too slow for large n.
Optimal Algorithm Steps
1) Use two pointers for a sliding window and an array count[26].
2) Expand right pointer; update character count and maxFreq.
3) If windowLen - maxFreq > k, shrink from left until valid.
4) Track maximum valid window length.
5) Return the best length.
Complexity Analysis
Time: O(n).
Space: O(1) (fixed 26 letters).
Common Pitfalls
- Recomputing maxFreq from scratch on every shrink (unnecessary).
- Using wrong validity condition (must be windowLen - maxFreq > k to shrink).
- Confusing “replace characters” with “delete characters”.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int left = 0, maxFreq = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
int idx = s.charAt(right) - 'A';
count[idx]++;
maxFreq = Math.max(maxFreq, count[idx]);
while ((right - left + 1) - maxFreq > k) {
count[s.charAt(left) - 'A']--;
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}func characterReplacement(s string, k int) int {
count := make([]int, 26)
left, maxFreq, ans := 0, 0, 0
for right := 0; right < len(s); right++ {
idx := int(s[right] - 'A')
count[idx]++
if count[idx] > maxFreq {
maxFreq = count[idx]
}
for (right-left+1)-maxFreq > k {
count[int(s[left]-'A')]--
left++
}
if right-left+1 > ans {
ans = right - left + 1
}
}
return ans
}class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> count(26, 0);
int left = 0, maxFreq = 0, ans = 0;
for (int right = 0; right < (int)s.size(); ++right) {
int idx = s[right] - 'A';
count[idx]++;
maxFreq = max(maxFreq, count[idx]);
while ((right - left + 1) - maxFreq > k) {
count[s[left] - 'A']--;
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = [0] * 26
left = 0
max_freq = 0
ans = 0
for right, ch in enumerate(s):
idx = ord(ch) - ord('A')
count[idx] += 1
max_freq = max(max_freq, count[idx])
while (right - left + 1) - max_freq > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
ans = max(ans, right - left + 1)
return ansvar characterReplacement = function(s, k) {
const count = new Array(26).fill(0);
let left = 0, maxFreq = 0, ans = 0;
for (let right = 0; right < s.length; right++) {
const idx = s.charCodeAt(right) - 65;
count[idx]++;
maxFreq = Math.max(maxFreq, count[idx]);
while ((right - left + 1) - maxFreq > k) {
count[s.charCodeAt(left) - 65]--;
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
};中文
题目概述
给定一个只含大写字母的字符串 s 和整数 k。你最多可以替换子串中的 k 个字符，使该子串所有字符相同。求可得到的最长子串长度。
核心思路
对窗口 [l..r]，设窗口内最高频字符出现次数为 maxFreq，则把窗口变成“全同字符”最少需要替换 windowLen - maxFreq 个字符。若该值 <= k，窗口有效。
暴力解法与不足
暴力枚举所有子串，并统计每个子串的最高频字符。复杂度约 O(n^2 * alphabet)，字符串较长时会超时。
最优算法步骤
1）使用双指针滑动窗口和 count[26] 计数。
2）右指针扩张窗口，更新计数与 maxFreq。
3）若 windowLen - maxFreq > k，左指针右移并收缩窗口。
4）持续更新最长有效窗口长度。
5）返回答案。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)（固定 26 个字母计数）。
常见陷阱
- 每次收缩都重算 maxFreq，导致实现复杂且效率下降。
- 窗口合法条件写错（应在 windowLen - maxFreq > k 时收缩）。
- 把“替换字符”误解成“删除字符”。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int left = 0, maxFreq = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
int idx = s.charAt(right) - 'A';
count[idx]++;
maxFreq = Math.max(maxFreq, count[idx]);
while ((right - left + 1) - maxFreq > k) {
count[s.charAt(left) - 'A']--;
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}func characterReplacement(s string, k int) int {
count := make([]int, 26)
left, maxFreq, ans := 0, 0, 0
for right := 0; right < len(s); right++ {
idx := int(s[right] - 'A')
count[idx]++
if count[idx] > maxFreq {
maxFreq = count[idx]
}
for (right-left+1)-maxFreq > k {
count[int(s[left]-'A')]--
left++
}
if right-left+1 > ans {
ans = right - left + 1
}
}
return ans
}class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> count(26, 0);
int left = 0, maxFreq = 0, ans = 0;
for (int right = 0; right < (int)s.size(); ++right) {
int idx = s[right] - 'A';
count[idx]++;
maxFreq = max(maxFreq, count[idx]);
while ((right - left + 1) - maxFreq > k) {
count[s[left] - 'A']--;
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = [0] * 26
left = 0
max_freq = 0
ans = 0
for right, ch in enumerate(s):
idx = ord(ch) - ord('A')
count[idx] += 1
max_freq = max(max_freq, count[idx])
while (right - left + 1) - max_freq > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
ans = max(ans, right - left + 1)
return ansvar characterReplacement = function(s, k) {
const count = new Array(26).fill(0);
let left = 0, maxFreq = 0, ans = 0;
for (let right = 0; right < s.length; right++) {
const idx = s.charCodeAt(right) - 65;
count[idx]++;
maxFreq = Math.max(maxFreq, count[idx]);
while ((right - left + 1) - maxFreq > k) {
count[s.charCodeAt(left) - 65]--;
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
};
Comments