Understanding the Problem

We need to find the longest substring where, after changing at most k characters, every character in the substring is the same. The key question is: for any given substring, what's the minimum number of changes needed to make all characters identical?

If a substring has length L and the most frequent character in it appears maxFreq times, then we need to change L - maxFreq characters to make the whole substring uniform. So the condition for a valid substring is: L - maxFreq <= k.

This reframing is the foundation for every approach. We're looking for the longest substring where the number of "non-majority" characters is at most k.

Key Constraints:

s.length up to 10^5 means O(n^2) is borderline. An O(n) or O(n log n) approach is preferred.
Only uppercase English letters (26 characters) means any per-character tracking is O(26) = O(1).
k can be as large as s.length, meaning we might be able to change every character. In that case, the answer is simply the entire string length.

Approach 1: Brute Force

Intuition

The most straightforward way: try every possible substring and check if it can be turned into a repeating character string with at most k replacements. For each starting index, expand the substring one character at a time, maintaining a frequency count. At each step, the number of replacements needed is windowLength - maxFrequency. Track the longest valid substring.

Algorithm

For each starting index left from 0 to n - 1
Initialize a frequency array of size 26 and a maxFreq variable
Expand right from left to n - 1, updating the frequency of s[right]
Update maxFreq to be the maximum value in the frequency array
If (right - left + 1) - maxFreq <= k, update the answer with the current window length
If (right - left + 1) - maxFreq > k, break (no point expanding further from this left)
Return the maximum length found

Example Walkthrough

1left=0: window="A", maxFreq=1, changes=0 <= 1, len=1

right

left

1/10

Code

Complexity Analysis

Time Complexity: O(n^2). For each of the n starting positions, we expand rightward up to n characters. The early break helps in practice but doesn't change worst-case behavior.
Space Complexity: O(1). The frequency array has a fixed size of 26, regardless of input size.

For each starting position, we're building the frequency count from scratch and expanding until the window becomes invalid. What if we could maintain the frequency count as we slide the window, instead of resetting it each time?

Approach 2: Sliding Window

Intuition

Instead of trying every starting point independently, we use two pointers to maintain a single window that we expand and shrink. The idea: expand right one step at a time. After each expansion, check if the window is still valid (windowSize - maxFreq <= k). If not, shrink from the left until it becomes valid again.

The frequency array updates incrementally. When right moves forward, we increment one count. When left moves forward, we decrement one count. No redundant work.

One subtlety: when we shrink the window by moving left forward, the maxFreq might decrease. We need to recompute it by scanning all 26 entries in the frequency array. Since 26 is a constant, this doesn't affect the overall O(n) time complexity.

Why does this work?

By maintaining the frequency count incrementally, we avoid recounting characters from scratch for each window position. The left pointer only moves forward, and the right pointer only moves forward, so each character is added and removed from the frequency array at most once. The while loop ensures we always have a valid window before recording its length.

Algorithm

Initialize a frequency array, left = 0, maxLen = 0
Iterate right from 0 to n - 1
Increment freq[s[right]]
Compute maxFreq as the maximum value in the frequency array
While (right - left + 1) - maxFreq > k, decrement freq[s[left]], increment left, and recompute maxFreq
Update maxLen = max(maxLen, right - left + 1)
Return maxLen

Example Walkthrough

1right=0: window="A", maxFreq=1, changes=0 <= 1, maxLen=1

right

left

1/10

Code

Complexity Analysis

Time Complexity: O(26 * n). Each character is added and removed from the window at most once, giving O(n) pointer movements. But each time we shrink the window, we scan all 26 frequency entries to find the new max. Since 26 is a constant, this is technically O(n), but the constant factor matters in practice.
Space Complexity: O(1). The frequency array is fixed at 26 entries regardless of input size.

Every time we shrink the window, we recompute maxFreq by scanning all 26 characters. But the answer can only improve when maxFreq increases. What if we just let maxFreq stay at its highest value and only update it upward?

Approach 3: Optimized Sliding Window

Intuition

This approach uses a clever observation: we never need to decrease maxFreq. Suppose the best valid window we've found so far has length bestLen. For the answer to improve, we need a window longer than bestLen. A longer valid window requires maxFreq to be higher (since windowSize - maxFreq <= k must hold, and we need a bigger windowSize). So any situation where maxFreq decreases is irrelevant to finding a better answer.

Instead of shrinking the window with a while loop until it's valid, we use an if statement. When the window is invalid, we move left forward by exactly one position (sliding the window) and move on. The window size either stays the same or grows. It never shrinks below the best valid size we've seen.

Why does this work?

The maxFreq variable acts as a "high watermark." It only goes up. When we slide the window (because it's invalid), the window size stays the same. We're essentially saying: "I've already found a valid window of this size. I won't settle for anything smaller. I'll only record a new best if I find a character frequent enough to justify an even bigger window."

When maxFreq does increase (because we encountered a character that appears more times in the current window than any character has in any previous window), the window might grow, potentially giving us a new best answer. This is the only time the answer can improve, and we handle it correctly by updating maxFreq and checking the window validity.

Algorithm

Initialize a frequency array, left = 0, maxFreq = 0, maxLen = 0
Iterate right from 0 to n - 1
Increment freq[s[right]] and update maxFreq if this character's count is the new max
If (right - left + 1) - maxFreq > k, decrement freq[s[left]] and increment left (slide window by 1)
Update maxLen = max(maxLen, right - left + 1)
Return maxLen

Example Walkthrough

1right=0: 'A', maxFreq=1, 1-1=0 <= 1, maxLen=1

right

left

1/8

Code

Complexity Analysis

Time Complexity: O(n). Both left and right move forward at most n times each. Each step does O(1) work (no scanning of the frequency array). Strictly linear.
Space Complexity: O(1). The frequency array is fixed at 26 entries.

Longest Repeating Character Replacement

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Sliding Window

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: Optimized Sliding Window

Intuition

Algorithm

Example Walkthrough

Code

Get Premium