Longest Repeating Character Replacement in Java: Explanation & Practice

Problem summary

Given a string and integer k, find the length of the longest substring containing the same letter after replacing at most k characters.

Starter code

public class Main {
    public static void main(String[] args) {
        String s = "AABABBA";
        int k = 1;
        
        // Window is valid if: windowSize - maxFreq <= k
        // maxFreq = frequency of most common char in window
        // Print: Length: 4
    }
}

Expected output and test cases

• AABABBA, k=1 → AABA or ABBA

  Length: 4

• ABAB, k=2 → AAAA or BBBB

  Length: 4

• AABABBA, k=0

  Length: 2

Hints

1. Keep track of count of each character in current window
2. Window is valid if we can make all chars same with ≤k changes
3. windowSize - maxCount = chars we need to replace
4. If invalid, shrink from left

Related Data Structures & Algorithms exercises

• Practice Longest Substring with K Distinct Characters in Java
• Practice Minimum Window Substring in Java
• Practice Fruit Into Baskets in Java

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler