We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Repeating Character Replacement

Number: 424

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg, Meta, Goldman Sachs, Uber, Microsoft, Apple, Yahoo, TikTok, Flipkart, Adobe, Yandex, Turing, MathWorks, Pocket Gems

Problem Description

Given a string s and an integer k, determine the length of the longest substring that can contain the same repeating letter after performing at most k character replacements. You can choose any character and change it to any other uppercase English letter.

Key Insights

  • Use a Sliding Window algorithm to keep track of a contiguous substring.
  • Maintain a frequency count of letters in the current window.
  • Keep track of the count of the most frequent character in the window.
  • If the current window size minus the maximum frequency is greater than k, shrink the window.
  • The maximum window size seen during the process is the answer.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string, since the window traverses the string in linear time. Space Complexity: O(1) because the frequency count for letters (A-Z) has a constant size.

Solution

The problem is solved using the sliding window technique. We initialize two pointers representing the left and right bounds of the current window. As we expand the window by moving the right pointer, we update the frequency count of the letter at the right pointer and track the letter that appears most frequently. The key observation is that the number of characters that need to be replaced in the current window is the window's size minus the count of the most frequently occurring letter. If this number exceeds k, we increment the left pointer to shrink the window until the condition is satisfied again. The maximum size of the window during the process gives the answer.

Code Solutions

# Python solution using the sliding window technique
def characterReplacement(s: str, k: int) -> int:
    # Dictionary to store frequency of characters in the current window
    char_counts = {}
    max_freq = 0  # Track the maximum frequency of a single character in the window
    max_length = 0
    left = 0  # Left pointer of the sliding window

    # Expand the sliding window with the right pointer
    for right in range(len(s)):
        # Count the current character
        char_counts[s[right]] = char_counts.get(s[right], 0) + 1
        # Update the max frequency in the current window
        max_freq = max(max_freq, char_counts[s[right]])
        
        # Check if the number of replacements needed exceeds k
        # (current window size) - (count of most frequent character) > k
        if (right - left + 1) - max_freq > k:
            # If condition fails, shrink the window by moving left pointer
            char_counts[s[left]] -= 1
            left += 1
        
        # Update the maximum length found so far
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example usage:
# print(characterReplacement("AABABBA", 1))  # Expected output: 4
← Back to All Questions