Back to solutions

Longest Repeating Character Replacement

MediumSliding Window

Find the longest substring where, after replacing at most k characters, all characters are the same.

Open problem
Constraints
  • 1 <= s.length <= 10^5
  • 0 <= k <= s.length

Sliding window with max frequency

Time O(n)Space O(1)

Grow a window and track the count of the most frequent character. The window is valid while its length minus that max count is at most k; otherwise shrink from the left.

#include <bits/stdc++.h>
using namespace std;

int characterReplacement(string s, int k) {
    vector<int> count(26, 0);
    int left = 0, maxFreq = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        maxFreq = max(maxFreq, ++count[s[right] - 'A']);
        while (right - left + 1 - maxFreq > k) count[s[left++] - 'A']--;
        best = max(best, right - left + 1);
    }
    return best;
}