Longest Repeating Character Replacement

Time: O(n)

Space: O(1)

Intuition

At any point in the sliding window, if the window size minus the count of the most-frequent character exceeds k, we cannot make that window valid with at most k replacements. So we track the highest frequency seen so far and use it to decide when the window is too large to shrink. The key insight is that we never shrink maxCount downward — we only need the window to grow.

Algorithm

1Initialize left = 0, maxCount = 0, maxLength = 0, and a freq[26] array.
2Expand right pointer one step at a time; increment freq[s[right] - A] and update maxCount.
3While (right - left + 1) - maxCount > k, the window needs more than k replacements: shrink by decrementing freq[s[left] - A] and incrementing left.
4Update maxLength = max(maxLength, right - left + 1).
5Return maxLength after the full traversal.

Example Walkthrough

Input: s = "AABABBA", k = 1

1.Expand to "AABAB" (size=5, maxCount=3 As): replacements needed = 5-3 = 2 > k. Shrink.
2.After shrink: "ABAB" (size=4, maxCount=2): 4-2=2 > 1. Shrink again.
3."BAB" (size=3, maxCount=2 Bs): 3-2=1 <= k. Valid. maxLength=3.
4.Continue... "ABBA" (size=4, maxCount=2 Bs): valid. maxLength=4.
5.Final answer is 4.

Output: 4

Common Pitfalls

•maxCount is never decremented even as the window shrinks — this is intentional and correct. We only care about windows at least as large as past valid ones.
•The condition checks (windowSize - maxCount) > k, not >= k.
•Input characters are uppercase A-Z; use s.charAt(i) - 'A' as the index.

Longest Repeating Character Replacement.java

Java


class Solution {

    // Approach: Sliding window tracking the most-frequent-character count;
    // window is valid when (size - maxCount) <= k. Shrink from left when invalid.
    // Time: O(n) Space: O(1)
    public int longestSubstr(String s, int k) {
        int[] freq = new int[26];
        int left = 0;
        int maxCount = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            int index = s.charAt(right) - 'A';
            freq[index]++;

            maxCount = Math.max(maxCount, freq[index]);

            // If more than k replacements needed → shrink window
            while ((right - left + 1) - maxCount > k) {
                freq[s.charAt(left) - 'A']--;
                left++;
            }

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

        return maxLength;
    }
}

Was this solution helpful?