Ecommet

Longest Repeating Character Replacement

Medium Problem 23 of 151 Java and Python

Problem

You are given a string s of uppercase English letters and an integer k. You may change any character into any other uppercase letter, at most k times in total.

Return the length of the longest substring containing a single repeated letter that you can get after these changes.

Example 1

Input
s = "ABAB", k = 2
Output
4
Why
Change both A's to B (or both B's to A).

Example 2

Input
s = "AABABBA", k = 1
Output
4
Why
Change the middle A to B to get "BBBB".

Constraints

  • 1 ≤ s.length ≤ 10⁵
  • 0 ≤ k ≤ s.length

Explanation

A window can be made uniform if window length - count of its most common letter ≤ k: keep the most common letter and change the rest.

Grow the window on the right; when it needs more than k changes, slide the left edge by one. The best window size only ever grows, so the most-common count does not need to be recomputed when the window shrinks.

Approach 1 · Naive

Every start, count as you grow

  • Time O(n²)
  • Space O(1)

For each start, extend the end while tracking letter counts and the highest count. A window is valid while length - maxCount <= k.

  1. For each i, reset 26 counts and maxCount.
  2. For each j ≥ i, add s[j], update maxCount, and if (j - i + 1) - maxCount <= k, update the best.
Java
class Solution {
    public int characterReplacement(String s, int k) {
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            int[] count = new int[26];
            int maxCount = 0;
            for (int j = i; j < s.length(); j++) {
                maxCount = Math.max(maxCount, ++count[s.charAt(j) - 'A']);
                if (j - i + 1 - maxCount <= k) {
                    best = Math.max(best, j - i + 1);
                }
            }
        }
        return best;
    }
}
Python
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        best = 0
        for i in range(len(s)):
            count = [0] * 26
            max_count = 0
            for j in range(i, len(s)):
                count[ord(s[j]) - ord('A')] += 1
                max_count = max(max_count, count[ord(s[j]) - ord('A')])
                if j - i + 1 - max_count <= k:
                    best = max(best, j - i + 1)
        return best

Approach 2 · Optimal

Sliding window

  • Time O(n)
  • Space O(1)

Expand right each step. If the window needs more than k replacements, move left once (dropping its letter). The window length never shrinks, so at the end it equals the best answer.

  1. Keep 26 counts, maxCount and left = 0.
  2. For each right: add s[right], update maxCount.
  3. If (right - left + 1) - maxCount > k, remove s[left] from the counts and increment left.
  4. Return n - left, the final window length.
Java
class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int maxCount = 0;
        int left = 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++;
            }
        }
        return s.length() - left;
    }
}
Python
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = [0] * 26
        max_count = left = 0
        for right, c in enumerate(s):
            count[ord(c) - ord('A')] += 1
            max_count = max(max_count, count[ord(c) - ord('A')])
            if right - left + 1 - max_count > k:
                count[ord(s[left]) - ord('A')] -= 1
                left += 1
        return len(s) - left

Complexity compared

ApproachTimeSpace
Naive Every start, count as you growO(n²)O(1)
Optimal Sliding windowO(n)O(1)

Key takeaways

  • maxCount may be stale after shrinking, and that is fine: only a larger maxCount can produce a larger answer.
  • Sliding by one instead of shrinking with a while keeps the window at the best size found so far.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem