Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is a string and a budget k. One operation lets us replace any single character with any other character. The goal is to find the longest substring that can be turned into a string of all one repeated character using at most k replacements.

That means the question is not “which character should each position become?” The real question is:

For some window in the string, how many characters are already equal to the most common character inside that window?

If a window has length window_size and its most frequent character appears max_count times, then the minimum number of replacements needed to make the whole window uniform is:

window_size - max_count

So the problem becomes: find the longest window where that value is at most k.

Why sliding window is the right idea

This is a classic “longest valid substring” shape. Whenever a problem asks for the longest contiguous range that satisfies some condition, a sliding window is usually the first tool to try.

Here the window is valid when:

current_window_length - highest_frequency_in_window <= k

As the right edge expands, the window may become invalid. When that happens, the left edge must move right until the window becomes valid again. That gives an O(n) scan instead of checking every substring.

The key observation that makes it fast

Inside the current window, only one character matters: the one with the highest frequency. If the best candidate character appears max_count times, every other character in the window would need to be replaced.

So there is no need to try all target characters explicitly. The window is good enough if it can be made uniform around its most common character within the replacement budget.

The standard implementation keeps a frequency map for characters currently in the window and a running max_count that records the largest count ever seen for any character while expanding the window.

That max_count is allowed to become slightly stale when the left edge moves. This is the subtle trick that often confuses people. It still works because a stale max_count can only make the window look a little more valid than it really is, which means the algorithm may delay shrinking but it never misses the true optimum. The best length recorded is still achievable by some window encountered during the scan.

How to derive this in an interview

A clean derivation goes in three steps.

First, notice that brute force is too expensive. If every substring is checked and its most frequent character is recomputed, the runtime becomes quadratic or worse.

Second, rewrite the condition in the most useful form. A substring can be made uniform if all characters except the majority character can be replaced, so the cost is window_length - max_frequency.

Third, realize that this condition behaves nicely under a sliding window. As the right edge moves, character counts change incrementally. If the window ever needs more than k replacements, shrinking from the left is the only move that can restore validity.

Once those three observations are on the table, the final algorithm is almost forced: keep counts, expand right, shrink left when needed, and record the best window length seen.

Python solution

from collections import defaultdict
from typing import DefaultDict


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        if k < 0:
            raise ValueError("k must be non-negative")

        left_index = 0
        best_window_length = 0
        max_char_frequency_in_window = 0
        character_counts: DefaultDict[str, int] = defaultdict(int)

        for right_index, current_char in enumerate(s):
            character_counts[current_char] += 1
            max_char_frequency_in_window = max(
                max_char_frequency_in_window,
                character_counts[current_char],
            )

            # If the window needs too many replacements, move the left edge
            # until the remaining window fits within the budget.
            while self._replacement_cost(
                left_index=left_index,
                right_index=right_index,
                max_char_frequency=max_char_frequency_in_window,
            ) > k:
                left_char = s[left_index]
                character_counts[left_char] -= 1
                if character_counts[left_char] == 0:
                    del character_counts[left_char]
                left_index += 1

            best_window_length = max(
                best_window_length,
                right_index - left_index + 1,
            )

        return best_window_length

    @staticmethod
    def _replacement_cost(
        left_index: int,
        right_index: int,
        max_char_frequency: int,
    ) -> int:
        window_length = right_index - left_index + 1
        return window_length - max_char_frequency

Why this works

At every step, the algorithm maintains a window [left_index, right_index] and the character counts inside that window.

When the window satisfies window_length - max_char_frequency_in_window <= k, it means the window can be converted into one repeated character using at most k replacements, so it is a valid candidate.

When the inequality is violated, the window is too expensive to fix. Shrinking from the left is the correct response because extending the window even further would only make it longer, and therefore no easier to repair.

Because each character enters the window once and leaves the window once, the two pointers move forward at most n times each. That is why the total runtime is linear.

Complexity

The runtime is O(n), where n is the length of the string, because each pointer only moves from left to right once.

The space complexity is O(1) for the original LeetCode constraints, since the string contains only uppercase English letters, so the frequency map never stores more than 26 keys. More generally, if the alphabet size is not fixed, the extra space is O(alphabet_size).

Interview follow-ups

What if the interviewer asks why the stale maximum frequency is still safe?

This is the most common follow-up because the running max_char_frequency is never decreased when the left side of the window moves. The explanation is that the algorithm uses that value only to decide when to shrink, not to construct the final string itself. A stale maximum can temporarily make the window look cheaper than it really is, so the code may shrink a little later than an exact implementation would. But that does not create a wrong answer. It only means the current window length is being compared against a maximum frequency that was valid for some earlier window ending at the same or an earlier position. As the scan continues, the algorithm still discovers the true best achievable length.

If an interviewer dislikes that proof technique, there is an exact variant that recomputes the highest frequency after each shrink. That version is easier to reason about formally, but it can be slower. With uppercase letters the extra scan is still effectively constant because there are only 26 counters. With a large alphabet, repeatedly recomputing the maximum makes the tradeoff much less attractive.

What if the interviewer wants the actual substring, not just the length?

The approach barely changes. Keep two extra variables to remember the best window boundaries whenever a longer valid window is found. At the end, return s[best_left:best_right + 1] instead of only the length.

This works because the sliding-window algorithm already identifies every window that is valid under the replacement budget. Recording the best boundaries is just additional bookkeeping layered on top of the same correctness argument.

The complexity stays O(n) time. The extra space remains O(1) for the standard uppercase-letter version. The only real tradeoff is that the code now tracks more state, which slightly increases implementation detail but not the core algorithmic idea.

What if the alphabet is very large or the string is general Unicode?

The same sliding-window strategy still works, but the implementation should use a hash map rather than a fixed-size array of 26 counters. That preserves the incremental update behavior even when characters are not confined to A-Z.

Why it still works is unchanged: the validity rule depends only on the window length and the frequency of the most common character in that window. A hash map is simply the right counting structure when the alphabet is sparse or unknown in advance.

The tradeoff is space. With uppercase English letters, the extra memory is effectively constant. With arbitrary Unicode or a large alphabet, the memory cost becomes proportional to the number of distinct characters present in the current window. The asymptotic runtime remains linear, but the constant factors from hashing are usually a bit higher than with a tiny fixed array.