Longest Repeating Character Replacement

Master this topic with zero to advance depth.

Longest Repeating Character Replacement

You are given a string s and an integer k. You can change at most k characters to any other uppercase English character. Return the length of the longest substring containing the same letter.

Visual Representation

s = "AABABBA", k = 1

[A A B A] B B A   (Len: 4, MaxFreq char 'A': 3)
 Window Size 4 - MaxFreq 3 = 1 (Matches k=1, VALID)

[A A B A B] B A   (Len: 5, MaxFreq char 'A': 3)
 Window Size 5 - MaxFreq 3 = 2 (Exceeds k=1, INVALID)

Medium

Examples

Input: s = "ABAB", k = 2
Output: 4
Replace the two 'A's with two 'B's or vice-versa.

Approach 1

Level I: Brute Force

Intuition

For every possible substring, check if we can make all characters in that substring the same by replacing at most k characters. To do this for a substring, we find the frequency of the most common character and check if (length - maxFreq) <= k.

Thought Process

Use two nested loops to iterate through all substrings [i, j].
For each substring, count character frequencies.
Find the character with the maximum frequency (maxFreq).
If (substringLength - maxFreq) <= k, the substring is valid.
Update maxLen accordingly.

⏱ O(26 * N^2)💾 O(1) - alphabet size map (26)

Detailed Dry Run

Substring	Freq Map	Max Freq	Len - MaxFreq	k	Valid?
"AAB"	{A:2, B:1}	2	3-2 = 1	1	YES
"AABA"	{A:3, B:1}	3	4-3 = 1	1	YES
"AABAB"	{A:3, B:2}	3	5-3 = 2	1	NO

java

public class Main {
    public static int characterReplacement(String s, int k) {
        int maxLen = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int[] count = new int[26];
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                maxFreq = Math.max(maxFreq, ++count[s.charAt(j) - 'A']);
                if ((j - i + 1) - maxFreq <= k) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(characterReplacement("AABABBA", 1)); // 4
    }
}

Approach 2

Level II: Binary Search on Answer (O(N log N * 26))

Intuition

We can binary search for the maximum possible length L of a valid substring. For a fixed length L, we use a sliding window of size L to check if at least one window satisfies (L - maxFreq) <= k. Finding maxFreq in a window takes O(26).

Thought Process

Search range for L is [0, n].
For each mid length step in binary search:
- Slide a window of size mid across the string.
- Count characters and find the most frequent character.
- If mid - maxFreq <= k, then length mid is possible.
Adjust the search range accordingly.

Pattern: Search on Answer Space

⏱ O(26 * N log N) - Binary search takes $\log N$ steps, each check takes $O(26 \times N)$.💾 O(1) - alphabet size map (26)

java

public class Solution {
    public int characterReplacement(String s, int k) {
        int low = 1, high = s.length(), res = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(s, k, mid)) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    private boolean check(String s, int k, int len) {
        int[] counts = new int[26];
        int maxFreq = 0;
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'A']++;
            if (i >= len) counts[s.charAt(i - len) - 'A']--;
            
            if (i >= len - 1) {
                maxFreq = 0;
                for (int count : counts) maxFreq = Math.max(maxFreq, count);
                if (len - maxFreq <= k) return true;
            }
        }
        return false;
    }
}

Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Instead of re-calculating everything, we use a sliding window [left, right]. We maintain the frequency of the most common character within the current window. The window is valid as long as (WindowLength - MaxFrequency) <= k. This works because WindowLength - MaxFrequency represents the minimum number of characters we need to replace to make all characters in the window the same.

Pattern: Variable Size Sliding Window

Expand: Increment frequency of s[right] and update maxFreq.
Constraint: (right - left + 1) - maxFreq > k
Shrink: Increment left and decrement its frequency. Note: maxFreq doesn't strictly need to be decreased, as only a larger maxFreq can increase our result.

⏱ O(N)💾 O(1) - alphabet size (26).

Detailed Dry Run

R	Char	Freq Map	Max Freq	Valid?	Action
0	A	{A:1}	1	Yes	Expand
1	A	{A:2}	2	Yes	Expand
2	B	{A:2, B:1}	2	Yes	Expand
3	A	{A:3, B:1}	3	Yes	Expand
4	B	{A:3, B:2}	3	No	Shrink L

java

public class Main {
    public static int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, maxFreq = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);
            
            // Window invalid? Shrink it
            if (right - left + 1 - maxFreq > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(characterReplacement("AABABBA", 1)); // 4
    }
}

⚠️ Common Pitfalls & Tips

You don't need to decrement maxFreq when shrinking the window. While this seems counter-intuitive, think about it: we only care about the largest maxFreq we've ever seen because that's the only way to get a larger maxLen.

← Previous QuestionFruit Into Baskets

Next Question →Find All Anagrams in a String

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.