Command Palette

Search for a command to run...

Hectal
Problem 7.4 · Sliding WindowMedium

Longest Repeating Character Replacement

PatternSliding Window: Variable SizeFrequency Counting

What it teaches: A window is valid when (length − count of its most common letter) ≤ k; the max count never needs to decrease.

Practise it on judges as “Longest Repeating Character Replacement”.

The problem

Given a string s of uppercase letters and an integer k, you may change up to k characters to any letter. Return the length of the longest substring of one repeated letter you can get.

Example 1

Input: s = "ABAB", k = 2
Output: 4

Example 2

Input: s = "AABABBA", k = 1
Output: 4

Change the 'B' in "AABA" to get "AAAA" (length 4).

Constraints

  • 1 ≤ s.length ≤ 10⁵
  • Uppercase letters
  • 0 ≤ k ≤ n

Pattern clues in the wording

  • → Longest substring with a budget of k changes
  • → Validity depends on letter counts in the window

These clues point to Sliding Window: Variable Size: Grow the window with the right pointer; when it breaks a rule, shrink it from the left until it's valid again.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
s = "ABAB"
k = 2
4
2
s = "AABABBA"
k = 1
4

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Optimal: window with a max-count · O(n)
1

Optimal: window with a max-count

Time O(n) Space O(26)

Count letters in the window and track maxCount, the highest count seen. If length − maxCount > k, move left by one (the window slides without growing). maxCount can stay stale: a longer answer requires a larger max count, so a stale value never causes a wrong larger answer.

Approach 1
class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, maxCount = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(right) - 'A']);
            if (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Verdict: Linear with a 26-letter count array.

Before you submit

Edge cases and common mistakes

Test these inputs

  • k = 0 (longest run of one letter)
  • k ≥ n (whole string)
  • One distinct letter

Mistakes people make

  • Recomputing maxCount by scanning 26 counts on every shrink (works, just slower).
  • Using a while loop that shrinks too far when maxCount is stale.

Interview

Follow-up questions

Why is it safe not to decrease maxCount when shrinking?