17.Longest Repeating Character Replacement

MediumBlind 75Sliding Window · 3/6

Problem

You are given a string s of uppercase English letters and an integer k. You may pick any character of the string and change it to any other uppercase letter, performing at most k such changes.

Return the length of the longest substring that can be made to contain one repeated letter after the changes.

Examples

Input:  s = "ABAB", k = 2
Output: 4
Explanation: Replace both 'A's with 'B' (or both 'B's with 'A') → "BBBB".

Input:  s = "AABABBA", k = 1
Output: 4
Explanation: Replace the 'A' at index 3 → "AABBBBA"; the substring "BBBB" has length 4.

Constraints

1 <= s.length <= 10^5
s consists of only uppercase English letters.
0 <= k <= s.length

💡 Key Insight

A window can be turned into one letter iff the number of characters that are not its most frequent letter fits in the budget: windowLength - maxFreq <= k. Slide a window, growing on the right and shrinking on the left whenever that condition breaks. Because we only care about windows that beat the current best, maxFreq never needs to be decreased — this makes each step O(1).

Brute Force

TimeO(n²)SpaceO(1)

Intuition

Fix a start index i, extend the end j one character at a time while maintaining letter counts and the highest count. The substring s[i..j] is valid when (j - i + 1) - maxCount <= k.

Algorithm

best = 0.
For each start i: reset count[26] and maxCount = 0.
For each end j >= i: increment count[s[j]], update maxCount; if (j - i + 1) - maxCount <= k, update best.
Return best.

Visualization

s = "AABABBA", k = 1

i=0: A A B A B ...  "AABA" needs 1 change ✓ len 4; "AABAB" needs 2 ✗
i=1: A B A B B ...  "ABAB" needs 2 ✗ ...
i=2: B A B B A      "BABB" needs 1 ✓ len 4
best = 4

Code

java

class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        int best = 0;
        for (int i = 0; i < n; i++) {
            int[] count = new int[26];
            int maxCount = 0;
            for (int j = i; j < n; j++) {
                int idx = s.charAt(j) - 'A';
                count[idx]++;
                maxCount = Math.max(maxCount, count[idx]);
                // characters that must be replaced = length - most frequent letter
                if ((j - i + 1) - maxCount <= k) {
                    best = Math.max(best, j - i + 1);
                }
            }
        }
        return best;
    }
}

Complexity

Time: O(n²) — all n(n+1)/2 substrings are examined.
Space: O(1) — a 26-slot count array.

Sliding Window (recompute max)

TimeO(26 · n)SpaceO(1)

Intuition

Validity is monotone: if a window is invalid, extending it further right keeps it invalid unless we drop characters from the left. So use two pointers. After adding s[right], while the window needs more than k replacements, remove s[left]. To know the current most-frequent count, scan the 26 counters.

Algorithm

left = 0, count[26], best = 0.
For each right:
- Increment count[s[right]].
- While (right - left + 1) - max(count) > k: decrement count[s[left]], left++.
- best = max(best, right - left + 1).
Return best.

Dry Run

s = "AABABBA", k = 1

right=0 A  [A]       max=1 len=1 ok  best=1
right=1 A  [AA]      max=2 len=2 ok  best=2
right=2 B  [AAB]     max=2 len=3 ok  best=3
right=3 A  [AABA]    max=3 len=4 ok  best=4
right=4 B  [AABAB]   max=3 len=5 ✗ → drop A → [ABAB] max=2 len=4 ✗ → drop A → [BAB] ok
right=5 B  [BABB]    max=3 len=4 ok  best=4
right=6 A  [BABBA]   max=3 len=5 ✗ → drop B → [ABBA] max=2 ✗ → drop A → [BBA] ok
best = 4

Code

java

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'A']++;
            // shrink while the window needs more than k replacements
            while ((right - left + 1) - maxOf(count) > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    private int maxOf(int[] count) {
        int max = 0;
        for (int c : count) {
            max = Math.max(max, c);
        }
        return max;
    }
}

Complexity

Time: O(26 · n) — each pointer moves at most n times and every check scans 26 counters.
Space: O(1) — fixed 26-slot array.

Sliding Window with Non-Decreasing maxFreqOptimal

TimeO(n)SpaceO(1)

Intuition

The answer can only grow when we find a window with a larger maxFreq (length ≤ maxFreq + k). So we may keep maxFreq as the highest count ever seen, even if it is stale after shrinking. A stale value only lets the window stay the same size — never report a bigger answer than a real window achieved. Also, the window never needs to shrink by more than one: use if instead of while, sliding the window forward at constant size.

Algorithm

left = 0, maxFreq = 0, count[26].
For each right:
- Increment count[s[right]]; maxFreq = max(maxFreq, count[s[right]]).
- If (right - left + 1) - maxFreq > k: decrement count[s[left]], left++ (window slides, size unchanged).
Return n - left (the final window size equals the best size).

Dry Run

flowchart TD
    A["s = 'AABABBA', k = 1"] --> B["right 0..3: 'AABA'<br/>maxFreq = 3, len 4 - 3 = 1 ok"]
    B --> C["right 4: 'AABAB'<br/>len 5 - 3 = 2 > k → drop 'A', left = 1"]
    C --> D["right 5: 'ABABB'<br/>count B = 3, len 5 - 3 = 2 > k → drop 'A', left = 2"]
    D --> E["right 6: 'BABBA'<br/>len 5 - 3 = 2 > k → drop 'B', left = 3"]
    E --> F["return n - left = 7 - 3 = 4"]

Code

java

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0;
        int maxFreq = 0; // highest single-letter count seen in any window
        for (int right = 0; right < s.length(); right++) {
            int idx = s.charAt(right) - 'A';
            count[idx]++;
            maxFreq = Math.max(maxFreq, count[idx]);
            // too many replacements needed: slide the window right by one
            if ((right - left + 1) - maxFreq > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
        }
        // window never shrinks, so its final size is the best size found
        return s.length() - left;
    }
}

Complexity

Time: O(n) — each character is processed once with O(1) work.
Space: O(1) — fixed 26-slot array.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Sliding Window (recompute max)	O(26 · n)	O(1)
Sliding Window (stale maxFreq)	O(n)	O(1)

Common Pitfalls

Trying to pick "the" target letter in advance — the best letter differs per window; the length - maxFreq formula handles all letters at once.
Worrying that a stale maxFreq gives wrong answers: it can only keep an invalid window at the same size as a previously valid one, so the returned maximum is still correct.
Using right - left instead of right - left + 1 for the window length.
Forgetting k can be 0; the formula still works (window must be a single repeated letter).