LeetCode 424 · Medium · Sliding Window

Longest Repeating Character Replacement

Given an uppercase string s and a budget k, you may change up to k characters into any letter. Return the length of the longest block of one repeated letter you can make.

O(n)time
O(26)space · letter counts
len − maxf ≤ kwindow stays valid

s: 1–20 uppercase letters A–Z · k: 0 to the length of s

−=

count letter counts inside the window · green = count equals maxf · dashed tiles in the window = the ones to replace · dashed outline = best so far

public int characterReplacement(String s, int k) { int[] count = new int[26]; int res = 0; int l = 0; int maxf = 0; // highest count seen in a window for (int r = 0; r < s.length(); r++) { count[s.charAt(r) - 'A']++; maxf = Math.max(maxf, count[s.charAt(r) - 'A']); while ((r - l + 1) - maxf > k) { count[s.charAt(l) - 'A']--; l++; } res = Math.max(res, r - l + 1); } return res;}
l
—
r
—
maxf
0
count
{}
res
0

Why it works

  1. Brute force checks every substring: a substring works if its length minus its most common letter's count is at most k. O(n²) substrings, each checked with 26 counts.
  2. Keep the most common letter, replace the rest. A window is valid when (r − l + 1) − maxf ≤ k. Grow r every step; when the window needs more than k replacements, drop letters from the left until it fits again.
  3. Why O(n): l and r only move right, so the inner loop does O(n) work in total. The count array has 26 slots.
  4. Pitfall, or rather a trick: maxf never goes down when the window shrinks, so it can be stale. That is safe: res only grows when a window beats the old best, which needs a real count above the old maxf.
  5. Related: Longest Substring Without Repeating Characters uses the same grow-right, shrink-left loop with a different validity test.