Example: Longest Repeating Character Replacement - rFronteddu/general_wiki GitHub Wiki

You are given a string s (consisting of uppercase English letters) and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Solution

• Index conversion Convert character to index by removing 'A'
• Frequency count we use an int[] to store the count of characters in the current window
• Sliding window expansion
  • for each char (right is end end of sliding window)
  • increment count of character
  • update max count
• Adjust window
  • While right - left + 1 - maxCount > k
    • resize window (at most we can replace k characters)
    • right - left + 1 is the current window size
    • right - left + 1 - maxCount is the number of char in the window that are not the most frequent
• Update max len
  • maxLength = Math.max(maxLength, right - left + 1)

public class Solution {
    public int characterReplacement(String s, int k) {
        // Array to store count of each character
        int[] count = new int[26];   
        // Max count of a single character in the current window
        int maxCount = 0;  
        // The result to store the maximum length of the substring
        int maxLength = 0;
        // Left boundary of the sliding window
        int left = 0; // Left boundary of the sliding window
        
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            count[rightChar - 'A']++;
            maxCount = Math.max(maxCount, count[rightChar - 'A']);
            
            // If the current window size minus the count of the most 
            // frequent character is greater than k
            while (right - left + 1 - maxCount > k) {
                char leftChar = s.charAt(left);
                count[leftChar - 'A']--;
                left++;
            }
            
            // Update the maxLength
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}