Problem Statement

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.

Additional information

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

Example 1:

Input: s = "ABAB", k = 2

Output: 4

Explanation: Replace the two 'A's with '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.

Brute Force

Intuition
We can check every possible substring to see if it can be converted into a valid repeating string. A substring is valid if the number of characters that need to be replaced is less than or equal to k. The number of replacements needed is the total length of the substring minus the count of the most frequent character in that substring.

Algorithm

1. Initialize max_len to 0.
2. Iterate i (start index) from 0 to n-1.
3. Iterate j (end index) from i to n-1.
4. For the substring s[i : j+1]:

• Count the frequency of every character.
• Find the character with the highest frequency (max_freq).
• Calculate replacements_needed = length_of_substring - max_freq.
• If replacements_needed <= k, update max_len.

5. Return max_len.

def character_replacement(s: str, k: int) -> int:
    n = len(s)
    res = 0
    
    for i in range(n):
        count = {}
        max_freq = 0
        for j in range(i, n):
            count[s[j]] = count.get(s[j], 0) + 1
            max_freq = max(max_freq, count[s[j]])
            
            length = j - i + 1
            if length - max_freq <= k:
                res = max(res, length)
            else:
                # If we already need too many replacements, 
                # extending the substring won't help if max_freq doesn't grow fast enough.
                # However, strictly for brute force logic, we can just continue or break.
                # Breaking is a small optimization but strictly checking all is O(N^2).
                break 
                
    return res

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: We verify O(n^2) substrings. Maintaining the count and max frequency inside the inner loop is constant time O(1) (limited to 26 characters).

• Space complexity: O(1)

• Reason: The dictionary size is limited to 26 uppercase English letters.

Sliding Window (Optimal)

Intuition
We can use a sliding window to expand a valid substring to the right. The condition for a window [l, r] to be valid is (window_length - max_frequency) <= k.
We expand the window by moving r to the right and updating the frequency of the new character. We track the max_frequency seen in the current window.
If the condition fails (i.e., we need more than k replacements), we shrink the window from the left by moving l forward until the condition is met again. This way, we only examine valid or near-valid windows.

Algorithm

1. Initialize count dictionary (or array of size 26).
2. Initialize l (left pointer) to 0.
3. Initialize res to 0 and max_f (max frequency in current window) to 0.
4. Iterate r (right pointer) from 0 to len(s) - 1.

• Update the count of s[r].

• Update max_f with the new count of s[r].

• Check if the window is invalid: (r - l + 1) - max_f > k.

• If invalid, decrease count of s[l] and increment l. We use if instead of while here because the window only ever becomes invalid by exactly 1 character (the one we just added). Shrinking by 1 is always sufficient.

• Update res = max(res, r - l + 1).

5. Return res.

def character_replacement(s: str, k: int) -> int:
    count = {}
    res = 0
    l = 0
    max_f = 0
    
    for r in range(len(s)):
        count[s[r]] = count.get(s[r], 0) + 1
        max_f = max(max_f, count[s[r]])
        
        # If replacements needed exceed k, shrink window by 1
        if (r - l + 1) - max_f > k:
            count[s[l]] -= 1
            l += 1
            
        res = max(res, r - l + 1)
        
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: The r pointer moves n times, and the l pointer moves at most n times.

• Space complexity: O(1)

• Reason: The dictionary stores at most 26 characters.