Technical Interview Question

You are given a string s and an integer k. You can replace at most k characters in the string s such that the resulting string contains the longest substring consisting of repeating characters. Write a function characterReplacement(s: str, k: int) -> int to find the length of the longest substring that can be formed.

Example:

Input: s = "ABAB", k = 2

Output: 4

Explanation: Replace two 'A's with two 'B's or vice versa.

Note:

• The string contains only uppercase English letters.
• Length of the string is between 1 and 10^4.
• The value of k is between 0 and the length of the string.

Answer

To find the length of the longest substring consisting of repeating characters, we can use the sliding window technique.

1. Initialize variables:

   • max_length = 0: to store the maximum length of the repeating substring.
   • max_count = 0: to store the maximum count of any single character within the current window.
   • start = 0: start index of the current window.
   • char_counts = {}: a dictionary to store the count of each character within the current window.

2. Iterate over the string s using a variable end as the end index of the current window:

   • Increment the count of the character at index end in char_counts.

   • Update max_count with the maximum count of any single character within the current window.

   • If the length of the current window (end - start + 1) minus max_count is greater than k, we need to shrink the window from the left side.

     • Decrement the count of the character at index start in char_counts.
     • Increment start to move the window to the right.

   • Calculate the current length of the repeating substring as end - start + 1.

   • Update max_length with the maximum of max_length and the current length.

3. Return max_length as the length of the longest substring that can be formed.

Python code:

def characterReplacement(s: str, k: int) -> int:
    max_length = 0
    max_count = 0
    start = 0
    char_counts = {}
    
    for end in range(len(s)):
        char_counts[s[end]] = char_counts.get(s[end], 0) + 1
        max_count = max(max_count, char_counts[s[end]])
        
        if (end - start + 1) - max_count > k:
            char_counts[s[start]] -= 1
            start += 1
        
        max_length = max(max_length, end - start + 1)
    
    return max_length

This solution has a time complexity of O(n) since we iterate over the string s exactly once.