We need to find the longest substring where, after changing at most k characters, every character in the substring is the same. For any given substring, how many changes are needed to make all characters identical?

If a substring has length L and the most frequent character in it appears maxFreq times, we keep those maxFreq characters and change the remaining L - maxFreq to match them. So a substring is valid when L - maxFreq <= k.

Every approach builds on this condition. We are looking for the longest substring where the number of non-majority characters is at most k.

Key Constraints:

Intuition

Try every possible substring and check whether it can be turned into a repeating-character string with at most k replacements. For each starting index, expand the substring one character at a time, maintaining a frequency count. At each step, the number of replacements needed is windowLength - maxFrequency. Track the longest valid substring. For a fixed start, every step adds 1 to the window length and at most 1 to maxFreq, so windowLength - maxFreq never decreases as the window grows. Once it exceeds k, it stays above k, so we stop and move the start forward.

Algorithm

Example Walkthrough

Code

For each starting position, this rebuilds the frequency count from scratch. The next approach keeps a single frequency count and reuses it as the window moves, instead of resetting it for every start.

Intuition

Instead of trying every starting point independently, we use two pointers to maintain a single window that we expand and shrink. The idea: expand right one step at a time. After each expansion, check if the window is still valid (windowSize - maxFreq <= k). If not, shrink from the left until it becomes valid again.

The frequency array updates incrementally. When right moves forward, we increment one count. When left moves forward, we decrement one count. No redundant work.

When we shrink the window by moving left forward, the maxFreq might decrease. We recompute it by scanning all 26 entries in the frequency array. Since 26 is a constant, this does not affect the overall O(n) time complexity.

Algorithm

Example Walkthrough

Code

Every time we shrink the window, we recompute maxFreq by scanning all 26 characters. The answer can only improve when maxFreq increases, so the next approach keeps maxFreq at its highest value seen so far and never recomputes it downward.

Intuition

We never need to decrease maxFreq. The answer is the largest window length ever recorded, and a window can only beat the current best if its length exceeds the best. Since a valid window of length L requires L - maxFreq <= k, a longer valid window needs a higher maxFreq. A smaller maxFreq can never produce a larger answer, so we can ignore it.

Instead of shrinking the window with a while loop until it is valid, we use a single if. When the window is invalid, we move left forward by exactly one position and continue. The window length then either stays the same or grows, never dropping below the largest valid length seen so far.

Algorithm

Example Walkthrough

Code