Longest Repeating Character Replacement

Find the longest substring that can be turned into one repeated letter with at most k changes, using a sliding window and the count of its most common letter.

The idea

To turn a window into one repeated letter, keep every copy of its most common letter and change all the others: that costs length − maxFreq changes. So the window is valid while length − maxFreq <= k. Grow on the right; when the window needs too many changes, drop one letter from the left. maxFreq is the highest count ever seen and is never lowered: the answer can only grow when some letter reaches a new, higher count.

Code

public static int CharacterReplacement(string s, int k) {
    var count = new int[26];
    int left = 0, maxFreq = 0, best = 0;
    for (int right = 0; right < s.Length; right++) {
        maxFreq = Math.Max(maxFreq, ++count[s[right] - 'A']);
        while (right - left + 1 - maxFreq > k) {
            count[s[left] - 'A']--;
            left++;
        }
        best = Math.Max(best, right - left + 1);
    }
    return best;
}

Tips

• Never lowering maxFreq is safe. A stale maxFreq can let an invalid window through, but that window is never longer than best, so it cannot raise the answer.
• Because the check fails by at most one each step, the while loop runs at most once per step, so the window never shrinks: it slides.
• count is an int[26] for capital letters; use a Dictionary<char,int> for a wider alphabet.

In the .NET library

s[right] - 'A' turns a char into an index 0..25 without any lookup. ++count[...] inside Math.Max increments first and passes the new value.