Problem

You are given a string s 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. (link)

Example 1:

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

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

Constraints:

• 1 <= s.length <= 10<sup>5</sup>
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Solution

For any window, keep the most frequent letter and replace the others:

Replacements needed = window length - highest character frequency

Window:       A A B A
Keep:         A A   A   (3 occurrences of A)
Replace:          B -> A
Result:       A A A A

4 - 3 = 1 replacement

A window is valid when the replacements needed are at most k.

Brute force Approach

Start at each index and extend the substring. Track character counts and the highest frequency. Stop when length - maxFrequency > k, because extending further cannot reduce the replacements needed.

Time: O(n²) expected in the worst case. Extra space: O(1), with at most 26 map entries.

class Solution {
    public int characterReplacement(String s, int k) {

        int n = s.length();
        int maxLength = 0;


        for(int i=0; i<n; i++){
            Map<Character, Integer> map = new HashMap<>();
            int maxFrequency = 0;
            for(int j=i; j<n; j++){

                char chr = s.charAt(j);
                int freq = map.getOrDefault(chr, 0) + 1;

                map.put(chr, freq);

                maxFrequency = Math.max(maxFrequency, freq);

                int length = j-i+1;
                int limit = length - maxFrequency;

                if(limit > k){
                    break;
                }

                maxLength = Math.max(maxLength, length);
            }
        }

        return maxLength;
    }

}

Better Approach

Use a sliding window from l to r:

1. Add the character at r to the frequency map.
2. While the window needs more than k replacements, remove characters from the left.
3. Update the maximum length once the window is valid.

getMaxFreq() recalculates the highest frequency in the current window. The separate maxFreq variable is updated but is not used in the validity check.

Time: O(26 × n), which is O(n) for 26 letters. Extra space: O(1).

class Solution {
    public int characterReplacement(String s, int k) {

        int n = s.length();
        int maxLength = 0;

        int l = 0;
        int r = 0;

        Map<Character, Integer> freqMap = new HashMap<>();
        int maxFreq = 0;

        while(r < n){
            char chr = s.charAt(r);
            int freq = freqMap.getOrDefault(chr, 0) + 1;

            freqMap.put(chr, freq);
            maxFreq = Math.max(maxFreq, freq);

            while((r-l+1 - getMaxFreq(freqMap)) > k){
                char leftChr = s.charAt(l);
                int leftFreq = freqMap.get(leftChr);

                if(leftFreq == 1){
                    freqMap.remove(leftChr);
                }
                else{
                    freqMap.put(leftChr, leftFreq-1);
                }

                l+=1;
            }

            maxLength = Math.max(maxLength, r-l+1);

            r+=1;

        }

        return maxLength;
    }

    private int getMaxFreq(Map<Character, Integer> freqMap){
        int maxFreq = 0;
        for(Map.Entry<Character, Integer> entry : freqMap.entrySet()){
            maxFreq = Math.max(maxFreq, entry.getValue());
        }

        return maxFreq;
    }

}

Optimal Approach

Keep a running maxFreq instead of scanning the map. If window length - maxFreq > k, move l once. Otherwise, the window can grow.

Why do we never decrease maxFreq? It records the highest frequency seen so far, so it may be larger than the current window's actual maximum. This can retain an invalid window at an already reached length. Once the window reaches maxFreq + k, it can grow again only if maxFreq increases. A stale value can preserve a length already achievable, but cannot create a falsely larger answer.

This approach finds the maximum length; the final window itself is not guaranteed to be valid.

Time: O(n) expected, without repeated frequency scans. Extra space: O(1).

class Solution {
    public int characterReplacement(String s, int k) {

        int n = s.length();
        int maxLength = 0;

        int l = 0;
        int r = 0;

        Map<Character, Integer> freqMap = new HashMap<>();
        int maxFreq = 0;

        while(r < n){
            char chr = s.charAt(r);
            int freq = freqMap.getOrDefault(chr, 0) + 1;

            freqMap.put(chr, freq);
            maxFreq = Math.max(maxFreq, freq);

            if((r-l+1 - maxFreq) > k){
                char leftChr = s.charAt(l);
                int leftFreq = freqMap.get(leftChr);

                if(leftFreq == 1){
                    freqMap.remove(leftChr);
                }
                else{
                    freqMap.put(leftChr, leftFreq-1);
                }

                l+=1;
            }

            if((r-l+1 - maxFreq) <= k)
                maxLength = Math.max(maxLength, r-l+1);

            r+=1;

        }

        return maxLength;
    }

}

Using Arrays

For uppercase English letters, use a 26-element array instead of a map. chr - 'A' maps A to index 0, B to 1, and so on.

This version follows the better approach: it recalculates the current maximum with getMaxFreq() while shrinking. It does not use the running maxFreq in the validity check.

Time: O(26 × n), which is O(n). Extra space: O(1).

class Solution {
    public int characterReplacement(String s, int k) {

        int n = s.length();
        int maxLength = 0;

        int l = 0;
        int r = 0;

        int[] freqMap = new int[26];
        int maxFreq = 0;

        while(r < n){
            char chr = s.charAt(r);
            freqMap[chr-'A'] += 1;
            maxFreq = Math.max(maxFreq, freqMap[chr-'A']);

            while((r-l+1 - getMaxFreq(freqMap)) > k){
                char leftChr = s.charAt(l);
                freqMap[leftChr-'A']-=1;
                l+=1;
            }

            maxLength = Math.max(maxLength, r-l+1);

            r+=1;

        }

        return maxLength;
    }

    private int getMaxFreq(int[] freqMap){
        int maxFreq = 0;
        for(int entry : freqMap){
            maxFreq = Math.max(maxFreq, entry);
        }

        return maxFreq;
    }

}