algoadvance

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 ‘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 longest substring is “BBBB”.

Constraints:

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

Clarifying Questions

1. Q: Can k be 0?
   • A: Yes, k can be 0. In this case, no replacements can be made.
2. Q: Is the input string always valid and non-empty?
   • A: Yes, per the constraints, the string will always have a length between 1 and 100,000.
3. Q: Are the characters in the string restricted to uppercase English letters only?
   • A: Yes, the string consists of only uppercase English letters.

Strategy

To solve this problem efficiently, we can use a sliding window approach. This approach helps us to maintain the longest window (substring) that can be converted to a repeating character string by performing at most k replacements.

Plan:

1. Initialize pointers: Use two pointers (left and right) to represent the current window in the substring.
2. Maintain a frequency count: Use a hashmap to count the frequencies of characters in the current window.
3. Expand the window: Move the right pointer to expand the window and update the frequency count.
4. Check validity: The window is valid if the length of the window minus the count of the most frequent character is less than or equal to k. If valid, update the maximum length found.
5. Shrink the window: If the window is not valid, increment the left pointer to shrink the window until it becomes valid.
6. Update result: Keep track of the maximum length of a valid window.

Algorithm:

• Start with both left and right pointers at the beginning of the string.
• Expand the window by moving the right pointer to the right.
• Use a hashmap to track the count of each character within the current window.
• Check if the current window is valid by calculating if the number of replacements needed (total window size minus frequency of the most frequent character) is within the allowed k.
• If invalid, move the left pointer to the right to reduce the window size until it becomes valid.
• Keep track of the maximum window size that is valid.

Code:

def characterReplacement(s: str, k: int) -> int:
    left = 0
    max_count = 0  # max frequency of a single character in the current window
    counts = {}
    max_length = 0

    for right in range(len(s)):
        counts[s[right]] = counts.get(s[right], 0) + 1
        max_count = max(max_count, counts[s[right]])
        
        # if window size minus the count of the most frequent character is greater than k, it's invalid
        while (right - left + 1) - max_count > k:
            counts[s[left]] -= 1
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

Time Complexity

• Time Complexity: O(n), where n is the length of the string. Each character is processed at most twice (once by the right pointer and once by the left).
• Space Complexity: O(1), because the hashmap will store at most 26 entries (one for each uppercase English letter).

This approach efficiently finds the longest substring that meets the criteria using the sliding window technique.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?