Longest Substring with Same Letters after Replacement

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.

Examples

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.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/kQzhDCYXlGU" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Sliding window with max frequency recalculation

Intuition

This problem is a variant of the problem [Longest Substring Without Repeating Characters](longest-substring-without-repeating-characters). We will use a similar sliding-window technique to solve this problem.

The sliding window approach is the optimal solution because we need to track the longest substring where we can replace characters to form contiguous identical characters. By dynamically adjusting the window size and keeping track of the character frequency, we can efficiently calculate the required result.

The max frequency of characters in the current window is recalculated every time the window size changes by iterating through the frequency counts. While this guarantees correctness, recalculating the max frequency on every iteration can be computationally a little expensive, but still constant ⇨ O(26) = O(1).

Approach

Here is the approach:

1. Track Character Frequencies:
   • Use a fixed-size frequency array (counts[26]) since there are only 26 uppercase English letters.
2. Expand Window:
   • For each new character added (s[r]), update its frequency in the counts array.
3. Check Validity:
   • Recalculate the maximum frequency from the counts (max(counts)).
   • If the number of changes (window size - max frequency) exceeds k, shrink the window by moving the l pointer and adjusting the frequency map.
4. Update Result:
   • Continuously update the answer (ans) using the valid window size.

Code

Java

class Solution {
    /**
     * Finds the length of the longest substring by re-evaluating 
     * max frequency on each iteration.
     */
    public int characterReplacement(String s, int k) {
        int[] counts = new int[26];
        int l = 0;
        int ans = 0;

        for (int r = 0; r < s.length(); r++) {
            // Add the new character to the window
            counts[s.charAt(r) - 'A']++;

            // Shrink the window as long as it's invalid.
            // We re-calculate the max frequency in each check.
            while ((r - l + 1) - max(counts) > k) {
                counts[s.charAt(l) - 'A']--;
                l++;
            }

            // The window is now valid, update the answer
            ans = Math.max(ans, r - l + 1);
        }

        return ans;
    }
    /**
     * Helper function to get the max frequency from the counts array.
     */
    private int max(int[] counts) {
        int max_val = 0;
        for (int count: counts) {
            max_val = Math.max(max_val, count);
        }
        return max_val;
    }
}

Python

class Solution:

    def characterReplacement(self, s: str, k: int) -> int:
        """
    Finds the length of the longest substring by re-evaluating 
    max frequency on each iteration.
    """
        counts = [0] * 26
        l = 0
        ans = 0

        for r in range(len(s)):
            # Add the new character to the window
            counts[ord(s[r]) - ord('A')] += 1

            # Shrink the window as long as it's invalid.
            # We re-calculate max(counts) in each check.
            while (r - l + 1) - max(counts) > k:
                counts[ord(s[l]) - ord('A')] -= 1
                l += 1

            # The window is now valid, update the answer
            ans = max(ans, r - l + 1)

        return ans

Complexity

• ⏰ Time complexity: O(26 * n) = O(n) for iterating through the string + O(26) for recalculating the max frequency at each step. Though linear in nature, recalculation adds overhead, making this approach slightly less efficient for long strings.
• 🧺 Space complexity: O(1) for the frequency array (fixed size counts[26]).

Method 2 - Sliding Window without max frequency recalculation

Intuition

Instead of recalculating the max frequency from the frequency map on every iteration, maintain a running value (maxCharCount) that tracks the highest frequency character seen within the current sliding window. This approach avoids frequent scanning of the frequency map, making it more efficient when dealing with large strings.

Approach

1. Track Character Frequencies:
   • Use a frequency HashMap to dynamically count characters in the current window.
   • Maintain a variable maxCharCount to store the highest frequency of any single character in the window.
2. Expand Window:
   • For each new character added (s[r]), update its frequency in the map and update maxCharCount if the frequency of the current character becomes higher.
3. Check Validity:
   • Calculate the number of changes (window size - maxCharCount).
   • If this exceeds k, shrink the window by decrementing the frequency of s[l] and adjusting the l pointer.
4. Update Result:
   • Continuously update the answer (ans) using the valid window size.

Code

Java

class Solution {
    public int characterReplacement(String s, int k) {
        HashMap<Character, Integer> freq = new HashMap<>(); // frequency map
        int l = 0;  // left pointer
        int maxCharCount = 0;  // max frequency of any char in window
        int ans = 0;  // result
        
        for (int r = 0; r < s.length(); r++) {  // right pointer
            char c = s.charAt(r);
            freq.put(c, freq.getOrDefault(c, 0) + 1);
            maxCharCount = Math.max(maxCharCount, freq.get(c));
            
            // Check if changes needed exceed k
            while ((r - l + 1) - maxCharCount > k) {
                char leftChar = s.charAt(l);
                freq.put(leftChar, freq.get(leftChar) - 1);
                l++;
            }
            
            ans = Math.max(ans, r - l + 1);
        }
        
        return ans;
    }
}

Python

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        freq: List[int] = [0] * 26 # Frequency map for characters
        max_freq: int = 0 # Maximum frequency count in the window
        
        ans: int = 0 # Result - max length of substring
        
        l: int = 0 # Left pointer
        
        for r in range(len(s)): # Right pointer
            freq[ord(s[r]) - ord('A')] += 1 # Update frequency of current character
            max_freq = max(max_freq, freq[ord(s[r]) - ord('A')]) # Update max frequency
            
            while (r - l + 1) - max_freq > k: # Invalid window condition
                freq[ord(s[l]) - ord('A')] -= 1 # Reduce frequency count
                l += 1 # Shrink the window
            
            ans = max(ans, r - l + 1) # Update maximum length
        
        return ans

Complexity

• ⏰ Time complexity: O(n), where n is the length of the string s. O(n). Each character is processed a fixed number of times (once when expanding and once when contracting the window).
• 🧺 Space complexity: O(1) as we only store character frequencies for uppercase English letters (26).