Longest Repeating Character Replacement

Longest Repeating Character Replacement

What is this problem about?

The Longest Repeating Character Replacement problem gives you a string of uppercase English letters and an integer k. You are allowed to replace any character in the string with any other uppercase English character, at most k times. Your goal is to find the length of the longest contiguous substring containing all identical characters after performing these operations.

Why is this asked in interviews?

This is a defining Sliding Window problem. Companies ask it because it forces candidates to figure out how to evaluate the "cost" of a window. It tests whether you can maintain a frequency map dynamically and use logic to determine if a window is valid. It perfectly highlights the difference between $O(N)$ and $O(N^2)$ problem-solving mindsets.

Algorithmic pattern used

This problem relies on the Sliding Window pattern combined with a Hash Table (or Frequency Array). As you expand your right pointer, you track the counts of all characters in the current window. The window is valid if WindowLength - MaxFrequencyCharacterCount <= k. This formula works because the most efficient way to make a window uniform is to keep the most frequent character and replace all the others. If the window becomes invalid, you increment the left pointer and update the frequencies.

Example explanation

String s = "AABABBA", k = 1.

• [A]: Len 1. MaxFreq=1 ('A'). $1 - 1 \le 1$. Valid. MaxLen=1.
• [AA]: Len 2. MaxFreq=2 ('A'). $2 - 2 \le 1$. Valid. MaxLen=2.
• [AAB]: Len 3. MaxFreq=2 ('A'). $3 - 2 \le 1$. Valid. MaxLen=3.
• [AABA]: Len 4. MaxFreq=3 ('A'). $4 - 3 \le 1$. Valid. MaxLen=4.
• [AABAB]: Len 5. MaxFreq=3 ('A'). $5 - 3 = 2 > 1$. Invalid! Move left.
• Window becomes [ABAB]: Len 4. MaxFreq=2 ('A' or 'B'). $4 - 2 = 2 > 1$. Invalid! Move left.
• Window becomes [BAB]: Len 3. MaxFreq=2 ('B'). $3 - 2 \le 1$. Valid. The maximum valid length found is 4.

Common mistakes candidates make

A major pitfall is recalculating the MaxFrequencyCharacterCount from scratch every time the left pointer moves. You don't need to decrement the historical max frequency! Because you only care about finding a longer valid window, the overall max frequency you've seen so far only needs to increase. If it decreases, the window size won't surpass your historical best anyway, so leaving the historical max frequency untouched keeps your algorithm strictly $O(N)$.

Interview preparation tip

To master the Longest Repeating Character Replacement interview question, memorize the core validity formula: (right - left + 1) - max_count <= k. Whenever you face a string replacement problem with a budget k, this mathematical derivation is almost always the key to unlocking the linear-time sliding window solution.