Longest Repeating Character Replacement

The "Longest Repeating Character Replacement" question is one of those string manipulation problems that sneak up on you. At first glance, it seems like a counting or brute-force challenge, but the optimal solution leans heavily on sliding window and frequency analysis. It’s a fantastic warm-up for mastering problems involving substrings and character frequency tracking, common themes in many real-world parsing and formatting systems.

Problem Statement

Given a string s and an integer k, you may choose at most k characters in the string and change them to any other uppercase English character. After doing so, return the length of the longest possible substring that contains only one repeating character.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Change two 'B's to 'A's to get "AAAA"

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Change one 'B' to 'A' to get "AABAAA"

1. Clarify Requirements Before Jumping Into Code

We’re allowed to change at most k characters to make the longest substring that is entirely the same character.

• Only uppercase letters are used, so we have a finite character space (A-Z).

• The output is the maximum length of such a transformed substring.

• The replacement doesn't need to be tracked, just return the length.

• We can only replace characters, not delete or rearrange.

2. Identify the Category of the Question

This is a sliding window problem with character frequency tracking.

It fits well into the category of "Longest Substring with X Constraint", which often relies on two pointers and a hash map or fixed-size array to track character counts.

Common patterns include:

• Sliding Window

• Hash Map or Frequency Array

• Greedy expansion/shrink based on window validity

3. Consider a Brute‑Force Approach to Understand the Problem

The brute-force option here is to try every possible substring and see if it can be turned into a uniform string with at most k changes.

How can we quickly determine how many changes are required to make a substring uniform?

Well, if we know what the most frequent character is in that substring, then the answer is every other character in the substring.

So let's count up the most frequent character, and determine the number of changes required by subtracting that count from the substring length.

In other words, for each substring:

• Count the most frequent character

• The number of changes required is equal to the substring length - max char count

• If changes ≤ k, update the max length

Time Complexity: O(n²) to check every substring

4. Brainstorm More Solutions

Our brute-force solution gave us a useful insight: we can take advantage of the fact that we don't need to know which characters are changing to calculate our answer. Instead, we can quickly determine how many changes are required to make a substring uniform using the formula substring length - max char count.

We also know that many versions of the "longest substring"question are able to optimize their runtime by relying on a sliding window approach. Let's try that here.

So we have a window. What do we do with that window?

• We can count up each character inside the window. Let's store those counts in a simple count[26] array.

• And from there, we can easily determine the most frequent character in the current window

At that point, we can easily calculate the number of required changes: substring length - max char count

If this number is ≤ k, then we know the window is valid. We can update our "max substring length" variable and expand the window to the right. Then we can see if we can achieve even longer substring with less than k changes.

But, if substring length - max char count is greater than k, then we're going to need to shrink the window. And we know we need to shrink the window from the left because if we shrink our window from the right, we end up with a substring that we've already checked.

Time Complexity: O(n) since both pointers move at most n steps

Space Complexity: O(26) for our counts array

So to summarize everything:

• Use a count[26] array to track character frequencies

• Use maxCount to store the max frequency in the current window

• Start our pointers at elements 0 and 1.

• While right pointer ≤ last element

  • Update our counts array and determine the count for the max character

  • if substring length - max char count  ≤ k

    • Update maxCount

    • Move right pointer forward

  • Otherwise, move the left pointer forward

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute-force	O(n²)	O(1)	Easy to understand	Unusable for large inputs
Sliding Window	O(n)	O(1)	Fast, optimal, clean logic	Requires frequency analysis

6. Write Pseudocode to Structure Your Thoughts

initialize count[26] = 0
left = 0, maxCount = 0, maxLen = 0

for right in 0 to s.length:
    increment count of s[right]
    update maxCount = max(maxCount, count[s[right]])

    while (window size - maxCount > k):
        decrement count of s[left]
        move left pointer

    update maxLen = max(maxLen, window size)

7. Consider Edge Cases

• All characters already the same → no need to replace

• k = 0 → longest stretch of identical characters

• k >= s.length → whole string can become uniform

• String contains only one type of character

8. Write Full Code Syntax (Java)

public class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, maxCount = 0, maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
			// Subtracting 'A' converts the character to an integer 
			// representing its position relative to 'A' in the 			
            // alphabet. For example, 'B' - 'A' = 1
            count[s.charAt(right) - 'A']++;

			// We only added one new character to the array, which 
			// means that new character is the only one that could 
			// have possibly replaced our maxCount
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);

			// Shrink our window until our maxCount is less than k 	
			// or we reach the right pointer
            while ((right - left + 1) - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }

			// update our max length
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

9. Test Your Code

System.out.println(characterReplacement("ABAB", 2));      // 4
System.out.println(characterReplacement("AABABBA", 1));   // 4
System.out.println(characterReplacement("AAAA", 2));      // 4
System.out.println(characterReplacement("ABCDE", 1));     // 2
System.out.println(characterReplacement("AAAB", 0));      // 3

10. Key Lessons to Remember for Future Questions

• When a problem asks for the longest substring under a modification constraint, consider a sliding window.

• Keep track of the most frequent character in the window — this lets you decide if the current window is valid.

• Only shrink the window when the number of replacements exceeds k.

• This technique generalizes to other problems like:

  • Longest Substring with At Most K Distinct Characters

  • Longest Substring with Character Replacement

  • Maximum Average Subarray

Good Luck and Happy Coding!