Longest Repeating Character Replacement in Java DSA

Solve Longest Repeating Character Replacement in Java DSA with a clear sliding window. Full step-by-step dry runs, simple pseudocode, and easy Java code for beginners.

1. Introduction

Longest Repeating Character Replacement in Java is a problem that feels tricky at first, but it clicks once you see the idea. You get a string and a number k. You may change up to k characters to any letter you want. Your job is to find the longest run where all letters become the same after those changes.

Let us make that real. Say the string is “AABABBA” and k is 1. You are allowed to swap one letter. The best you can do is turn one letter and get a block of four same letters. So the answer is 4.

The catch is that you do not actually change the string. You only count. For any window of letters, you check one thing: how many letters would you need to change to make them all equal? That number is the window size minus the count of its most common letter. If that number is k or less, the window is valid.

We will solve it in two ways. First a brute force that checks every window, which is slow but easy to trust. Then a sliding window that scans the string once and stays fast. Both get a full, step-by-step dry run on the same seven-letter string, so you can watch every count change and see why the answer lands at 4.

2. Understanding the Problem

Let us fix the rules before any code.

• You get a string s and a number k, for example s = “AABABBA” and k = 1.
• At most k characters may be replaced with any uppercase letter.
• The goal is the longest substring that becomes all one letter after those replacements.
• Those replaced letters do not all have to be the same, and they can sit anywhere inside the window.

For our pair the answer is 4. Inside “AABABBA” the window “AABA” has three A’s and one B. Change that one B to an A and you get four A’s in a row. That uses only one change, which fits k = 1.

3. Concepts You Need Here

3.1 The Key Formula: Replacements Needed

Take any window of letters. To make them all equal, keep the most common letter and change the rest. So the number of changes you need is simple.

replacements needed = window length - count of most common letter

A window is valid when that number is k or less. This one line is the heart of the whole problem.

• If a window of size 4 has 3 A’s, you need 4 – 3 = 1 change.
• When that 1 is within k, the window works.

3.2 Counting Letters in a Window

The input here is uppercase English letters, so we can count with a small int array of 26 slots. Slot 0 is A, slot 1 is B, and so on. To turn a letter into its slot we use ch minus ‘A’.

• count[ch – ‘A’] holds how many times that letter appears in the current window.
• The biggest value in that array is the count of the most common letter.

4. Approach 1: Check Every Window (Brute Force)

The plain idea is to try every possible window. For each start index, grow the window one letter at a time. For each window, count the letters, find the most common one, and check if the replacements needed fit within k. Track the longest valid window as you go.

4.1 Pseudocode

best = 0

for start in 0 .. n-1:
    count = array of 26 zeros
    for end in start .. n-1:
        count[s[end] - 'A'] += 1
        windowLen = end - start + 1
        maxFreq = largest value in count
        if windowLen - maxFreq <= k:
            best = max(best, windowLen)

return best

4.2 Pseudocode Explained

We test every window by picking a start and stretching the end.

• Picking a start. The outer loop fixes where the window begins. We reset the counts for each fresh start.
• Stretching the end. The inner loop adds one letter at a time and bumps its count.
• Checking the window. We find the most common letter, work out the changes needed, and compare with k.
• Saving the best. When the window is valid and longer than what we had, we update best.

4.3 Java Code

public class LongestRepeatingBrute {

    public static int characterReplacement(String s, int k) {
        int n = s.length();
        int best = 0;
        for (int start = 0; start < n; start++) {
            int[] count = new int[26];
            for (int end = start; end < n; end++) {
                count[s.charAt(end) - 'A']++;
                int windowLen = end - start + 1;
                int maxFreq = 0;
                for (int c : count) {
                    maxFreq = Math.max(maxFreq, c);
                }
                if (windowLen - maxFreq <= k) {
                    best = Math.max(best, windowLen);
                }
            }
        }
        return best;
    }

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

4.4 Java Code Explained

This is the same plan in Java. It uses two loops to build every window and a small inner loop to find the most common letter.

• Line 5 sets best to 0, which is our answer so far.
• The outer loop on line 6 fixes the window start.
• A fresh count array is built on line 7 for each new start, so old counts do not leak in.
• Then line 8 runs the inner loop that stretches the window end.
• Line 9 adds the new end letter into its slot using s.charAt(end) – ‘A’.
• Lines 12 to 14 walk all 26 slots to find maxFreq, the count of the most common letter.
• Line 15 checks the formula. If windowLen minus maxFreq fits within k, the window is valid.
• Finally line 16 saves the window length when it beats the current best.

4.5 Dry Run of the Brute Force

Let us trace every window that starts at index 0, using s = “AABABBA” and k = 1. The string has 7 letters. We grow the end one step at a time and check each window.

So the start = 0 pass already finds a valid window of length 4. The brute force keeps going with start = 1, start = 2, and so on, but no window ever beats 4. For example, start = 2 finds the window “BABB” (three B’s, one A) which is also length 4 and valid, but it just ties.

4.6 Reading the Dry Run

Let us walk the start = 0 pass step by step, because it is where the answer shows up.

end = 0, add A.

• The window is just “A”, so A’s count is 1.
• The most common letter is A with maxFreq 1.
• Changes needed are 1 – 1 = 0, which fits k. So best becomes 1.

end = 1, add A.

• Now the window is “AA”, so A climbs to 2.
• maxFreq is 2 and the length is 2, so changes needed are 0.
• The window is valid and longer, so best becomes 2.

end = 2, add B.

• The window is “AAB” with A at 2 and B at 1.
• The most common letter is still A, so maxFreq stays 2.
• Changes needed are 3 – 2 = 1, which equals k. So best becomes 3.

end = 3, add A.

• The window is “AABA”, so A jumps to 3 and B stays at 1.
• maxFreq is now 3, the biggest so far in this pass.
• Changes needed are 4 – 3 = 1, still within k. So best becomes 4, our final answer.

end = 4, add B.

• The window is “AABAB” with A at 3 and B at 2.
• maxFreq is 3, but the window length is now 5.
• Changes needed are 5 – 3 = 2, which is more than k. So the window is not valid and best does not change.

end = 5, add B.

• The window “AABABB” now has A at 3 and B at 3.
• maxFreq is 3 and the length is 6, so changes needed are 3.
• That is over k, so again this window is skipped.

end = 6, add A.

• The full string “AABABBA” has A at 4 and B at 3.
• maxFreq rises to 4 but the length is 7, so changes needed are 3.
• Still over k, so the window fails and best stays at 4.

Notice how the changes needed grew as the window got longer. Early on, one B was cheap to fix. Later, too many odd letters piled up and broke the limit. The brute force found the answer, but it recounted the whole window from scratch every time, which is wasted effort.

💡 Interview Insight If asked why brute force is slow here, point to the inner loop that scans all 26 slots for maxFreq on every single window. That extra work stacks up and pushes the time cost higher.

4.7 Time and Space Cost

• Time is O(n squared), because every start pairs with every end, and we scan counts inside.
• Space is O(1), since the count array is always 26 slots no matter how long the string is.

The brute force is easy to trust, but it redoes the same counting again and again. Next we fix that with a sliding window that never looks back.

5. Approach 2: The Sliding Window

The smart idea is to keep one window and slide it across the string. We use two pointers, lower and higher, that mark the window edges. We move higher forward to add letters. When the window needs more than k changes, we move lower forward to drop a letter and shrink it. That way each letter is visited a small, fixed number of times.

5.1 Pseudocode

count = array of 26 zeros
lower = 0
maxFreq = 0
best = 0

for higher in 0 .. n-1:
    count[s[higher] - 'A'] += 1
    maxFreq = max(maxFreq, count[s[higher] - 'A'])

    while (higher - lower + 1) - maxFreq > k:
        count[s[lower] - 'A'] -= 1
        lower += 1

    best = max(best, higher - lower + 1)

return best

5.2 Pseudocode Explained

Think of the window as a stretchy band. The right edge keeps growing. The left edge only moves when the window breaks the rule.

• Adding a letter. Each step brings higher forward and bumps that letter’s count.
• Tracking the top count. maxFreq remembers the highest count we have ever seen in the window.
• Shrinking when needed. If the window needs more than k changes, we drop the left letter and slide lower forward.
• Saving the best. After each step the window is valid again, so we record its length if it is the longest.

One thing surprises people: we never lower maxFreq when we shrink. That is fine. The best answer can only grow, so a slightly stale maxFreq never causes a wrong result. It just keeps the code simple and fast.

5.3 Java Code

public class LongestRepeatingSliding {

    public static int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int lower = 0;
        int maxFreq = 0;
        int best = 0;
        for (int higher = 0; higher < s.length(); higher++) {
            int idx = s.charAt(higher) - 'A';
            count[idx]++;
            maxFreq = Math.max(maxFreq, count[idx]);
            while ((higher - lower + 1) - maxFreq > k) {
                count[s.charAt(lower) - 'A']--;
                lower++;
            }
            best = Math.max(best, higher - lower + 1);
        }
        return best;
    }

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

5.4 Java Code Explained

The code is short because one loop does everything. The higher pointer is the loop variable and lower slides only when it has to.

• Line 4 makes the 26-slot count array, all zeros to start.
• Next, line 5 sets lower to 0, the left edge of the window.
• On line 6 we set maxFreq to 0, the highest letter count seen so far.
• Then line 8 runs the loop with higher, the right edge that keeps moving.
• Lines 9 and 10 find the slot for the new letter and add one to it.
• Line 11 updates maxFreq if this letter’s count is a new high.
• Lines 12 to 15 are the shrink loop. While the window needs more than k changes, we remove the lower letter and slide lower forward.
• Finally line 16 records the window length in best if it is the longest valid one yet.

5.5 Dry Run of the Sliding Window

Let us trace the whole run on s = “AABABBA” and k = 1. The window starts empty with lower = 0. Each row shows what happens after higher moves one step. When the window breaks the rule, the shrink column shows the letter we drop and where lower lands.

Legend: higher is the right edge, lower is the left edge, window is higher minus lower plus 1, and need is window minus maxFreq.

The counts in the last three rows show the window after the shrink. Before each shrink the window was size 5, which needed 2 changes and broke the k = 1 rule. After dropping one letter the window is back to size 4, which needs only 1 change and is valid again.

5.6 Reading the Dry Run

Let us go step by step and watch the window grow, then hold steady at size 4.

higher = 0, add A.

• A’s count becomes 1, so maxFreq is 1.
• The window “A” needs 1 – 1 = 0 changes, which fits k.
• No shrink is needed, so best becomes 1.

higher = 1, add A.

• A climbs to 2, so maxFreq rises to 2.
• The window “AA” needs 0 changes, so it is valid.
• Since nothing breaks, best becomes 2.

higher = 2, add B.

• B enters with count 1, while A stays at 2, so maxFreq stays 2.
• The window “AAB” needs 3 – 2 = 1 change, which equals k.
• The window is still valid, so best becomes 3.

higher = 3, add A.

• A jumps to 3, so maxFreq rises to 3.
• The window “AABA” needs 4 – 3 = 1 change, still within k.
• No shrink happens, so best becomes 4. This is the answer.

higher = 4, add B.

• B rises to 2 while A is 3, so maxFreq stays 3.
• The window “AABAB” is size 5 and needs 5 – 3 = 2 changes, which breaks the rule.
• So we shrink: drop the letter at lower (an A) and move lower to 1. Now the window is “ABAB” of size 4, which needs only 1 change and is valid again. best stays 4.

higher = 5, add B.

• B rises to 3, but maxFreq is already 3, so it stays 3.
• The window grows to size 5 and needs 2 changes, breaking the rule once more.
• Again we shrink: drop the A at lower and move lower to 2. The window is back to size 4 and valid, so best stays 4.

higher = 6, add A.

• A rises back to 2 while B is 3, so maxFreq stays 3.
• The window is size 5 again and needs 2 changes, so the rule breaks.
• We shrink one last time: drop the B at lower and move lower to 3. The window returns to size 4 and best stays 4.

See the pattern in the second half. Once best reached 4, the window never shrank below size 4 and never grew past it. Each time higher added a letter that made the window too costly, lower slid forward by exactly one to fix it. The window kept its size and glided across the string, which is why the sliding window is so fast.

💡 Interview Insight A common question is why we do not shrink maxFreq when lower moves. Explain that best can only ever increase, so a stale maxFreq never shrinks the answer. It may keep the window a touch larger than strictly valid, but that never produces a wrong best.

5.7 Time and Space Cost

• Time is O(n), because higher and lower each move forward at most n times across the whole run.
• Space is O(1), since the count array is always 26 slots.

This is a big jump from the brute force. We went from O(n squared) down to O(n) by never recounting old letters. The window remembers what it holds and updates only at the edges.

6. Comparing the Two Approaches

Both approaches return the same answer. They just pay different prices to get there.

In an interview, mention the brute force first to show you understand the problem. Then move to the sliding window as your real answer. Explain the replacements formula clearly, since that is the insight the interviewer is really testing.

7. Common Mistakes and Edge Cases

A few small traps catch beginners on this problem. Keep them in mind.

• Forgetting the formula and trying to track which letters to change, instead of just counting the most common one.
• Shrinking maxFreq when the window shrinks, which adds needless work and can slow the code.
• Moving lower more than one step per outer loop, when a single shrink is enough each time.
• Using the 26-slot array on lowercase or mixed input, which breaks the ch minus ‘A’ math.
• An empty string returns 0, and a string of all same letters returns its full length.

Run an all-same string and an empty string through your code before you call it done. Those edge cases catch more bugs than any ordinary input.

8. FAQ’s

9. Conclusion

Longest Repeating Character Replacement in Java teaches a habit you will reuse across many problems: keep a window and count what is inside it. Once you see that changes needed equal window length minus the most common letter count, the whole thing falls into place.

Our seven-letter trace showed the payoff clearly. The brute force checked every window and found 4, but it recounted from scratch each time. The sliding window found the same 4 in one pass, sliding lower forward only when the window broke the rule.

So take the pattern, not just the answer. When a problem asks for the longest or shortest window under some rule, reach for two pointers and a running count. That sliding window habit will serve you well on the harder problems waiting further down the list.

10. Further Reading

• LeetCode Longest Repeating Character Replacement — practice the original problem and submit your own solution.
• Oracle Java arrays documentation — the official reference for working with arrays in Java.
• Previous in this series: Longest Substring Without Repeating Characters in Java DSA
• Next in this series: Reverse Linked List in Java — flip a linked list by rewiring its pointers one node at a time.