DSA Series Day 11: Longest Repeating Character Replacement in Java, Python and Rust

Welcome to Day 11 of the Tekraze DSA series, where we solve Longest Repeating Character Replacement in Java, Python and Rust. Yesterday we met the sliding window with Longest Substring Without Repeating Characters. Today we push the same idea one step further.

Longest Repeating Character Replacement is a favourite interview question because it tests whether you really understand when a window is valid.

Also Read: Longest Substring Without Repeating Characters: 6 Best Tips (Day 10 of this series)

What is the Longest Repeating Character Replacement problem?

You get a string s of uppercase English letters and a number k. You may change any character into any other uppercase letter, at most k times. Return the length of the longest substring that can become one repeating letter after those changes. This is LeetCode problem 424.

Input:  s = "ABAB", k = 2
Output: 4
Why:    change both A to B (or both B to A) to get "BBBB"

Input:  s = "AABABBA", k = 1
Output: 4
Why:    change the one B inside "AABA" to get "AAAA"

How should you think about Longest Repeating Character Replacement in plain words?

Look at any window of the string. To make it all one letter, the cheapest plan is to keep the letter that appears most and replace everything else.

So the number of changes a window needs is its size minus the count of its most common letter. If that number is at most k, the window is fine and can grow. If it goes over k, slide the left edge forward until it is fine again.

Also Read: Data Structures Cheat Sheet: 11 Best Structures, Made Easy for a quick look at arrays and hash maps

What does the brute force solution for Longest Repeating Character Replacement look like?

Try every substring, count its letters, and check if size minus the top count fits within k.

def replace_brute(s, k):
    best = 0
    for i in range(len(s)):
        count = [0] * 26
        top = 0
        for j in range(i, len(s)):
            c = ord(s[j]) - 65
            count[c] += 1
            top = max(top, count[c])
            if (j - i + 1) - top <= k:
                best = max(best, j - i + 1)
    return best

The brute force approach to Longest Repeating Character Replacement takes O(n²) time because every start index scans forward. Space is O(1) since the count array always has 26 slots. That is fine for short strings and slow for long ones.

How do we get the optimal sliding window solution for Longest Repeating Character Replacement?

Keep a count array for the current window, a left pointer and maxFreq, the highest count seen so far. Move right one step at a time and update the count and maxFreq.

While window size minus maxFreq is more than k, drop the leftmost letter and move left forward. Then record the window size as a possible answer.

A neat detail is that maxFreq never needs to go down. The answer only improves when some letter reaches a higher count than before, so a slightly stale maxFreq can never produce a wrong, bigger answer.

Time is O(n) because each pointer moves across the string once. Space is O(1) for the fixed 26 slot array. If you want a refresher on why two nested loops become one linear pass, read our Big O helper post on time and space complexity.

Dry run: Longest Repeating Character Replacement on “AABABBA” with k = 1

Here is what the window does, step by step. Notice that maxFreq stays at 3 even after the window shrinks. That is the stale value we just talked about, and it is harmless.

right	Letter added	Window after shrinking	maxFreq	Best so far
0	A	“A”	1	1
1	A	“AA”	2	2
2	B	“AAB”	2	3
3	A	“AABA”	3	4
4	B	“ABAB” (dropped first A)	3	4
5	B	“BABB” (dropped second A)	3	4
6	A	“ABBA” (dropped a B)	3	4

The final answer is 4, which matches the expected output.

Java solution for Longest Repeating Character Replacement

The Java version uses a plain int[26] array and Math.max to track maxFreq.

public class Solution {
    public static int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, maxFreq = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);
            // shrink when the letters we must replace exceed k
            while (right - left + 1 - maxFreq > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
    public static void main(String[] args) {
        String[] tests = {"ABAB", "AABABBA", "AAAA", "", "A", "ABCDE", "ABBB"};
        int[] ks = {2, 1, 0, 2, 0, 1, 2};
        int[] want = {4, 4, 4, 0, 1, 2, 4};
        for (int i = 0; i < tests.length; i++) {
            int got = characterReplacement(tests[i], ks[i]);
            System.out.println((got == want[i] ? "PASS " : "FAIL ") + tests[i] + " k=" + ks[i] + " -> " + got);
        }
    }
}

Python solution for Longest Repeating Character Replacement

Python’s defaultdict keeps the counting short, since missing letters start at zero.

from collections import defaultdict

def character_replacement(s: str, k: int) -> int:
    count = defaultdict(int)
    left = max_freq = best = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        max_freq = max(max_freq, count[ch])
        # shrink when the letters we must replace exceed k
        while (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

if __name__ == "__main__":
    tests = [("ABAB", 2, 4), ("AABABBA", 1, 4), ("AAAA", 0, 4), ("", 2, 0),
             ("A", 0, 1), ("ABCDE", 1, 2), ("ABBB", 2, 4)]
    for s, k, want in tests:
        got = character_replacement(s, k)
        print("PASS" if got == want else "FAIL", s, "k=", k, "->", got)

Rust solution for Longest Repeating Character Replacement

Rust works on the raw bytes of the string, so each letter maps to an index with b - b'A'. See the Rust standard library docs if fixed size arrays are new to you.

fn character_replacement(s: &str, k: i32) -> i32 {
    let b = s.as_bytes();
    let mut count = [0i32; 26];
    let (mut left, mut max_freq, mut best) = (0usize, 0i32, 0i32);
    for right in 0..b.len() {
        let i = (b[right] - b'A') as usize;
        count[i] += 1;
        max_freq = max_freq.max(count[i]);
        // shrink when the letters we must replace exceed k
        while (right - left + 1) as i32 - max_freq > k {
            count[(b[left] - b'A') as usize] -= 1;
            left += 1;
        }
        best = best.max((right - left + 1) as i32);
    }
    best
}

fn main() {
    let tests = [("ABAB", 2, 4), ("AABABBA", 1, 4), ("AAAA", 0, 4), ("", 2, 0),
                 ("A", 0, 1), ("ABCDE", 1, 2), ("ABBB", 2, 4)];
    for (s, k, want) in tests {
        let got = character_replacement(s, k);
        println!("{} {} k={} -> {}", if got == want { "PASS" } else { "FAIL" }, s, k, got);
    }
}

All three Longest Repeating Character Replacement programs use the same seven tests: “ABAB” with k 2, “AABABBA” with k 1, “AAAA” with k 0, an empty string, “A” with k 0, “ABCDE” with k 1 and “ABBB” with k 2. Every test passed in Java, Python and Rust.

What are the 6 best tips for an easy Longest Repeating Character Replacement solution?

1. Spot the pattern. A longest continuous substring plus a budget of changes or mistakes almost always means a sliding window.
2. Remember the one formula. Changes needed equals window size minus the most frequent letter count. Everything else follows from it.
3. Do not recompute maxFreq on shrink. Keeping the old high value is safe and saves you a scan of the array.
4. Use a fixed array. With only uppercase letters, an int array of 26 beats a hash map for speed and clarity.
5. Test the edges. Try an empty string, k equal to 0, k larger than the string, and all different letters.
6. Say the invariant first. In an interview, state the window rule out loud, size minus top count must stay within k, and then code it. Interviewers love hearing the invariant before the loop.

What are the common mistakes people make with Longest Repeating Character Replacement?

• Counting the changes as the number of distinct letters instead of size minus the top count.
• Trying to decide which letter to keep up front, instead of letting the counts decide.
• Rescanning all 26 counts every step to fix maxFreq, then worrying it is wrong when it is not.
• Mixing up if and while, which moves left too far or not far enough.
• Forgetting that k can be 0, which turns the problem into the longest run of one letter.

Where is the Longest Repeating Character Replacement pattern used in the real world?

A window with an error budget shows up a lot. Data cleaning tools look for the longest stretch of readings that stays mostly consistent while allowing a few bad values. DNA and text analysis search for long regions that match a pattern with a few mismatches.

Quality checks on production lines flag the longest run of good items with only a handful of defects. Uptime reports use the same idea to find the longest healthy period that tolerates a small number of failed checks.

Which earlier posts in the series should you read?

Begin with Day 1, Two Sum for the hash map basics and Day 2, Best Time to Buy and Sell Stock for tracking the best answer in one pass. Day 3, Contains Duplicate, Day 4, Valid Anagram and Day 5, Group Anagrams build the counting toolkit we use today.

The two pointer moves that sliding windows grow out of are in Day 6, Valid Palindrome, Day 7, Two Sum II, Day 8, 3Sum and Day 9, Container With Most Water. Then read Day 10, Longest Substring Without Repeating Characters right before this one. Now that Longest Repeating Character Replacement is done, we finish sliding windows next and then step into stacks.

Frequently asked questions

What is the time complexity of Longest Repeating Character Replacement?

The sliding window solution for Longest Repeating Character Replacement runs in O(n) time and O(1) space because the count array has a fixed 26 slots. The brute force method takes O(n²) time.

Why is the window valid when size minus maxFreq is at most k?

The cheapest way to make a window one letter is to keep its most common letter and change the rest. The rest is size minus maxFreq, so that must fit within k.

Why don’t we decrease maxFreq when the window shrinks?

A stale maxFreq can only keep the window the same size, never make the answer larger than it should be. The answer grows only when a letter truly reaches a new higher count.

What happens when k is 0?

No changes are allowed, so the answer is simply the longest run of the same letter in the string.

Is this problem related to Longest Substring Without Repeating Characters?

Yes. Both use a sliding window with two pointers. Only the rule for a valid window changes, from all letters unique to size minus top count within k.