Crack the Backend

Problem Statement

Given a string s (uppercase letters) and an integer k, you can change at most k characters to any other letter. Return the length of the longest substring that can be made to contain only the same letter after at most k changes.

We are finding a substring such that, if we could change at most k characters inside it, the whole substring could become one repeated letter.
So for a window to be valid: the number of characters that are not the majority must be <= k (those can be changed to match).

Key Observations

In any window, the minimum number of changes to make all letters the same is windowLength - maxFrequency (change every non-majority character to the majority). The window is valid if windowLength - maxFrequency <= k.
Expand with right; when (length - maxFreq) > k, shrink left until the condition holds again. Track the maximum window size.
Max frequency in the window can be updated when we add/remove characters, or by scanning the 26-sized freq array (still O(1) per step).

Approach

High-level: Maintain a window where windowLength - maxFrequencyInWindow <= k. Expand with right; when the condition fails, shrink left. Track the maximum window length.

Steps:

Freq map (e.g. int[26]) for the current window; left = 0, maxFreq = 0, best = 0.
For each right: increment freq[s[right]], update maxFreq. While (right - left + 1) - maxFreq > k, decrement freq[s[left]], left++ (and optionally recompute maxFreq).
best = max(best, right - left + 1). Return best.

Implementation

Java

public int characterReplacement(String s, int k) {
    int[] freq = new int[26];
    int left = 0, maxFreq = 0, best = 0;

    for (int right = 0; right < s.length(); right++) {
        maxFreq = Math.max(maxFreq, ++freq[s.charAt(right) - 'A']);

        while (right - left + 1 - maxFreq > k) {
            freq[s.charAt(left) - 'A']--;
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

Test Cases

Example 1

Input

s = "ABAB", k = 2

Expected

4

Explanation

Replace two A's or B's to get "AAAA" or "BBBB".

Complexity Analysis

Time: O(n).
Space: O(1) (26 letters).

Follow-ups

What if k is very large (same as length)?