Longest Substring with Same Letters After Replacement

Given a string and an integer k, find the length of the longest substring in which all characters are the same after replacing at most k characters.

The problem is a sliding window with one non-obvious property: the window never has to shrink more than one step, and the frequency maximum it depends on can be allowed to go stale without changing the answer. That second part is the interesting bit and the part most explanations skip.

The problem

Input:  s = "aabccbb", k = 2
Output: 5      -> replace both c's: "aabbbbb" contains "bbbbb"

Input:  s = "abbcb", k = 1
Output: 4      -> replace the c: "abbbb" contains "bbbb"

Input:  s = "abccde", k = 1
Output: 3      -> replace one character in "bcc" or "ccd"

Why brute force is too slow

Every substring, and for each one the count of its most frequent character:

static int bruteForce(String s, int k) {
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        int[] freq = new int[26];
        int maxFreq = 0;
        for (int j = i; j < s.length(); j++) {
            freq[s.charAt(j) - 'a']++;
            maxFreq = Math.max(maxFreq, freq[s.charAt(j) - 'a']);
            if ((j - i + 1) - maxFreq <= k) {
                best = Math.max(best, j - i + 1);
            }
        }
    }
    return best;
}

O(n²), and it already contains the key insight: a window of length L whose most frequent character appears maxFreq times needs L - maxFreq replacements, the window is valid when that is at most k.

The sliding window

Keep a window and a frequency table. Extend on the right; when the window becomes invalid, move the left edge by one.

static int longestSubstring(String s, int k) {
    int[] freq = new int[26];
    int left = 0, maxFreq = 0, best = 0;

    for (int right = 0; right < s.length(); right++) {
        freq[s.charAt(right) - 'a']++;
        maxFreq = Math.max(maxFreq, freq[s.charAt(right) - 'a']);

        // window length minus the most frequent character = characters to replace
        if ((right - left + 1) - maxFreq > k) {
            freq[s.charAt(left) - 'a']--;
            left++;
        }

        best = Math.max(best, right - left + 1);
    }
    return best;
}

O(n) time, O(1) space, the table is 26 entries regardless of input length.

Why the window shrinks by one, not by a loop

The usual sliding-window template shrinks with a while. Here an if is enough, and the reason is what the algorithm is actually computing.

The answer only ever grows. Once a valid window of length L has been seen, a shorter window can never improve on it, so there is no value in shrinking the window below L. It can simply slide along at that width looking for a place where it becomes valid again.

Each iteration adds one character on the right. If that makes the window invalid, removing one from the left restores the previous width, the window therefore never shrinks; it grows or stays the same, and best is exactly the final width.

A while loop is also correct and does the same work with more shrinking. The if version is not an optimisation of the running time, both are O(n). It is a consequence of only needing the maximum.

The stale maximum

The line that looks wrong:

maxFreq = Math.max(maxFreq, freq[s.charAt(right) - 'a']);

maxFreq is never decreased when a character leaves the window on the left. After a slide it can be larger than the true maximum inside the current window, which makes (length - maxFreq) too small and can leave an invalid window looking valid.

That is real and it does not affect the answer.

The reason: maxFreq only fails to decrease. An over-large maxFreq makes the condition too permissive, so the window is not shrunk when it perhaps should be, but the window’s width does not grow either, because best is only updated to the current width. For the answer to become wrong, some window would have to be reported as valid at a width greater than any genuinely valid window, and that requires maxFreq to exceed a value it actually held at some earlier point. It cannot: it is a running maximum of real counts from real windows.

In other words the algorithm may carry a window that is no longer valid, and that window is never wider than the best genuinely valid window already recorded. Recomputing the true maximum on every slide, an O(26) scan, gives the same answer and is slower.

This is worth being able to explain rather than merely recite, because it is the standard follow-up question.

Handling any character set

The - 'a' indexing assumes lowercase ASCII. For arbitrary input, a map:

static int longestSubstring(String s, int k) {
    Map<Character, Integer> freq = new HashMap<>();
    int left = 0, maxFreq = 0, best = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        freq.merge(c, 1, Integer::sum);
        maxFreq = Math.max(maxFreq, freq.get(c));

        if ((right - left + 1) - maxFreq > k) {
            freq.merge(s.charAt(left), -1, Integer::sum);
            left++;
        }

        best = Math.max(best, right - left + 1);
    }
    return best;
}

Same shape, O(1) space becomes O(alphabet), and the constant factor is noticeably worse.

The off-by-one

Two mistakes produce answers that are close enough to look plausible:

Window length as right - left. It is right - left + 1. Both ends are inclusive. This under-reports by exactly one and passes any test whose answer happens to be checked loosely.

Updating best before the shrink. The measurement has to come after the window has been made valid, or an invalid window’s width is recorded. Placing the best update at the end of the loop body makes the ordering unambiguous.

Tracing it

The behaviour is easier to trust after watching it on the second example, s = "abbcb", k = 1:

right	char	window	maxFreq	length − maxFreq	action	best
0	a	a	1	0	—	1
1	b	ab	1	1	—	2
2	b	abb	2	1	—	3
3	c	abbc	2	2 > 1	drop a	3
4	b	bbcb	3	1	—	4

Row 3 is the shrink: the window is invalid, one character leaves on the left, and the width returns to three rather than continuing to fall. Row 4 shows the payoff — the window slides into a region where it becomes valid again and immediately reaches four.

The stale maximum is visible too. After row 3 the window is bbc, whose true maximum is 2, and maxFreq is already 2 so nothing is stale yet. Change the input to "abbcaa" and maxFreq outlives the a that produced it — and the reported answer is still correct, for the reason above.

Writing the trace out is the fastest way to check an implementation: if the best column ever exceeds the width of a window you can verify by hand, the bug is the off-by-one below.

The related problems

The same window with a different validity condition solves a family:

• Longest substring with at most k distinct characters — validity is map.size() <= k, and this one does need a while, because the window can require several removals.
• Longest substring without repeating characters — validity is that no count exceeds one.
• Maximum consecutive ones after flipping k zeros — the binary special case of this exact problem, with maxFreq being the count of ones.

Recognising that last equivalence is usually worth more than memorising either solution.

Related: the 0/1 knapsack problem for the other standard shape. More in the algorithms guides.

Frequently asked questions

What is the time complexity?

O(n). Each index enters the window once and leaves at most once, and the frequency update is constant time.

What is the space complexity?

O(1) with a fixed 26-entry array, or O(alphabet) with a map for arbitrary characters.

Why is the condition length - maxFreq > k?

length - maxFreq is the number of characters that are not the most frequent one, which is exactly how many replacements the window needs.

Why does the window shrink by one instead of in a loop?

The answer never decreases, so there is no value in a window narrower than the best already found. Removing one character restores the previous width and the search continues at that width.

Is a while loop wrong here?

No, just unnecessary. It produces the same answer with more shrinking and the same asymptotic cost.

Why is maxFreq never decreased?

Because an over-large value only makes the condition more permissive, and the window’s width never exceeds a width that was genuinely valid earlier. The answer is unaffected.

Would recomputing maxFreq each slide be more correct?

It would track the true maximum and return the same answer, at the cost of a scan per slide. The stale version is correct for this question, not merely faster.

What does k = 0 give?

The longest run of a single repeated character, since no replacements are allowed.

How does this relate to “max consecutive ones after flipping k zeros”?

It is the same algorithm over a two-character alphabet, with maxFreq being the count of ones in the window.

What is the most common bug?

Computing the window length as right - left instead of right - left + 1, or updating the best length before the window has been made valid.