Longest Repeating Character Replacement

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.

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 <= 105
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Approach: Sliding Window with Frequency Tracking

Algorithm

1. Use a sliding window with left and right pointers
2. Maintain the frequency of characters in the window and track the most frequent character count (maxFreq)
3. Expand the right pointer
4. If windowSize - maxFreq > k, too many characters would need changing; shrink from the left
5. Track the maximum window size seen

Time & Space Complexity

• Time Complexity: O(n) - single pass with two pointers
• Space Complexity: O(1) - fixed-size frequency array of 26 uppercase letters

Java Implementation

public class LongestRepeatingCharacterReplacement {

    /**
     * Return the length of the longest substring with the same letter
     * after at most k replacements.
     * @param s Input string
     * @param k Maximum allowed replacements
     * @return Longest possible length
     */
    public static int characterReplacement(String s, int k) {
        int[] freq = new int[26];
        int left = 0;
        int maxFreq = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            int idx = s.charAt(right) - 'A';
            freq[idx]++;
            maxFreq = Math.max(maxFreq, freq[idx]);

            int windowSize = right - left + 1;
            if (windowSize - maxFreq > k) {
                freq[s.charAt(left) - 'A']--;
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: s = \"ABAB\", k = 2");
        System.out.println("Output: " + characterReplacement("ABAB", 2)); // Expected: 4

        System.out.println("Input: s = \"AABABBA\", k = 1");
        System.out.println("Output: " + characterReplacement("AABABBA", 1)); // Expected: 4
    }
}

Example Walkthrough

For s = "ABAB", k = 2:

1. right=0 ‘A’: maxFreq=1, window=1, 1-1=0 <= 2. maxLen=1
2. right=1 ‘B’: maxFreq=1, window=2, 2-1=1 <= 2. maxLen=2
3. right=2 ‘A’: maxFreq=2, window=3, 3-2=1 <= 2. maxLen=3
4. right=3 ‘B’: maxFreq=2, window=4, 4-2=2 <= 2. maxLen=4

Answer: 4 (replace the two ‘A’s to ‘B’ or vice versa).

Key Points

1. Replacement Bound: A window is feasible if windowSize - maxFreq <= k
2. maxFreq Is Approximate: Since the window only shrinks, maxFreq need not be recomputed exactly
3. O(1) Space: Only 26 counters are needed for uppercase letters
4. Longest Substring Pattern: Expand, shrink only when invalid, then update the answer
5. Shrinking Preserves Max: The window never needs to shrink below the best answer found so far