☕ DSA Java Articles

Topics › Sliding Window and Two Pointers › Medium Problems

Longest Repeating Character Replacement

Hard TUF ID 927 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

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, at most k times in total. Return the length of the longest substring that consists of a single repeated letter after these changes.

The key reformulation: for a fixed substring of length len, the cheapest way to make it uniform is to keep its most frequent letter and change everything else. That costs len - maxFreq changes. So the question becomes: what is the longest substring with len - maxFreq ≤ k?

Constraints: 1 ≤ |s| ≤ 10^5, 0 ≤ k ≤ |s|.

Example 1

s = "ABAB", k = 2
answer = 4          // change both A's to B (or both B's to A): "BBBB"

Example 2

s = "AABABBA", k = 1
answer = 4          // change the A at index 3: "AABBBBA" contains "BBBB"

Approach 1: Brute force

Intuition. Fix the start i and extend j. Maintain the count of each letter in s[i..j] and the largest of those counts. The substring is fixable if (j - i + 1) - maxFreq ≤ k. Once the cost exceeds k, extending further never helps: adding one character raises the length by one and raises maxFreq by at most one, so the cost never goes down. That justifies the break.

Algorithm.

  1. For each start i: reset freq[26] and maxFreq.
  2. For j = i ..: increment freq[s[j]], update maxFreq, compute changes = (j - i + 1) - maxFreq.
  3. If changes > k, break; otherwise update best.
static int bruteForce(String s, int k) {
    int n = s.length(), best = 0;
    for (int i = 0; i < n; i++) {
        int[] freq = new int[26];
        int maxFreq = 0;
        for (int j = i; j < n; j++) {
            maxFreq = Math.max(maxFreq, ++freq[s.charAt(j) - 'A']);
            int changes = (j - i + 1) - maxFreq;   // letters that differ from the majority letter
            if (changes > k) break;
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Complexity. Time O(n^2): with a large k the inner loop rarely breaks. Space O(26).

Approach 2: Better, shrinking sliding window

Intuition. The condition len - maxFreq ≤ k is monotonic in the usual sense: shrinking a valid window keeps it valid (removing one letter lowers the length by one and lowers maxFreq by at most one), and growing an invalid window keeps it invalid. So a two-pointer window works. Extend r; while the window costs more than k, drop s[l] and move l right.

The difficulty is that maxFreq can drop when a letter leaves the window, and a running maximum cannot be decreased cheaply. Since there are only 26 letters, we simply rescan the frequency array after each left step.

Algorithm.

  1. l = 0, freq[26], maxFreq = 0, best = 0.
  2. For each r: increment freq[s[r]] and update maxFreq.
  3. While (r - l + 1) - maxFreq > k: decrement freq[s[l]], increment l, recompute maxFreq over all 26 counts.
  4. Update best with r - l + 1.
static int better(String s, int k) {
    int[] freq = new int[26];
    int l = 0, maxFreq = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        maxFreq = Math.max(maxFreq, ++freq[s.charAt(r) - 'A']);
        while ((r - l + 1) - maxFreq > k) {
            freq[s.charAt(l) - 'A']--;
            l++;
            maxFreq = 0;
            for (int f : freq) maxFreq = Math.max(maxFreq, f);
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Complexity. Time O(26 · n): l moves at most n times in total and each move costs a 26-step rescan. Space O(26).

Approach 3: Optimal, a max frequency that never decreases

Intuition. Two observations remove the rescan.

First, as in other “longest window” problems, we never need the window to shrink. If we have already found a valid window of length L, only a window of length L + 1 or more can improve the answer, so when the window turns invalid we slide it one step (move l once) and keep its length.

Second, and this is the surprising part, we never need to decrease maxFreq. Keep it as “the highest count any letter has ever reached inside the window”. It can then be larger than the true maximum of the current window, which looks dangerous. Two short arguments show it is not.

So best grows exactly when a valid longer window exists, and the slow 26-step rescan disappears.

Algorithm.

  1. Same state as Approach 2.
  2. For each r: increment freq[s[r]], raise maxFreq if needed.
  3. If (r - l + 1) - maxFreq > k: decrement freq[s[l]] and increment l once. Do not touch maxFreq.
  4. Update best with r - l + 1.
static int optimal(String s, int k) {
    int[] freq = new int[26];
    int l = 0, maxFreq = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        maxFreq = Math.max(maxFreq, ++freq[s.charAt(r) - 'A']);
        if ((r - l + 1) - maxFreq > k) {           // slide by one; maxFreq may now be stale, which is fine
            freq[s.charAt(l) - 'A']--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Dry run on s = "AABABBA", k = 1:

r char freq (A,B) maxFreq len before slide? l best
0 A 1,0 1 1 no 0 1
1 A 2,0 2 2 no 0 2
2 B 2,1 2 3 no 0 3
3 A 3,1 3 4 no 0 4
4 B 3,2 3 5 yes, drop A 1 4
5 B 2,3 3 5 yes, drop A 2 4
6 A 2,3 3 5 yes, drop B 3 4

The window never grows beyond 4 because no letter ever beats the record count 3 with only one change allowed; the answer is 4.

Complexity. Time O(n): one pass, constant work per character. Space O(26).

Edge cases and pitfalls