Problem Description

You have a string s consisting of uppercase English letters and an integer k representing the maximum number of character replacements you can make.

The task is to find the length of the longest substring where all characters are the same, after performing at most k character replacements. You can change any character in the string to any other uppercase English character, but you're limited to k such operations.

For example, if you have the string "ABAB" and k = 2, you could replace both 'B's with 'A's to get "AAAA", which gives you a substring of length 4 with all same characters. Alternatively, you could replace both 'A's with 'B's to get "BBBB", also resulting in length 4.

The goal is to strategically choose which characters to replace to maximize the length of a contiguous substring containing only one unique character.

Intuition

The key insight is to think about what makes a valid window. For any substring to contain all same characters after at most k replacements, we need to keep the most frequent character in that substring and replace all others.

If we have a window of size window_size and the most frequent character appears max_freq times, then we need exactly window_size - max_freq replacements to make all characters the same. This must be at most k.

This leads us to the condition: window_size - max_freq ≤ k

We can use a sliding window approach where we expand the window by moving the right pointer. As we include each new character, we update its count and track the maximum frequency of any character in the current window.

When our window becomes invalid (requires more than k replacements), we need to shrink it from the left. The clever part is that we don't need to shrink the window completely until it's valid again - we can just move both pointers together, maintaining the window size. This works because:

1. We're looking for the maximum window size
2. Once we've found a valid window of size x, we're only interested in windows larger than x
3. By maintaining the window size when it becomes invalid and sliding it forward, we're essentially searching for a better solution

The algorithm naturally expands the window when possible and slides it forward when necessary, eventually leaving us with l pointing to a position where n - l gives us the maximum valid window size found during the entire traversal.

Solution Approach

We implement a sliding window solution using two pointers with the following components:

Data Structures:

• A hash table cnt (Counter) to track the frequency of each character in the current window
• Variables l and r for left and right pointers of the window (though r is implicit in the enumeration)
• Variable mx to maintain the maximum frequency of any character in the current window

Algorithm Steps:

1. Initialize: Start with an empty counter cnt, left pointer l = 0, and maximum frequency mx = 0.

2. Expand Window: Iterate through the string with index r and character c:

   • Add the character to our window: cnt[c] += 1
   • Update the maximum frequency: mx = max(mx, cnt[c])

3. Check Window Validity: After adding each character, check if the window is valid:

   • Window size = r - l + 1
   • Characters to replace = r - l + 1 - mx
   • If characters to replace > k, the window is invalid

4. Shrink Window When Invalid: When r - l + 1 - mx > k:

   • Remove the leftmost character from the count: cnt[s[l]] -= 1
   • Move the left pointer right: l += 1
   • Note: We only shrink by one position, maintaining the largest valid window size found so far

5. Calculate Result: After processing all characters, the answer is len(s) - l

   • This works because the window maintains the maximum valid size throughout
   • The final position of l gives us the starting position of a window that extends to the end of the string

Key Pattern - Sliding Window Optimization:

The algorithm uses an optimized sliding window where we don't shrink the window back to a valid state completely. Instead, we maintain the window at the maximum size found so far, sliding it forward when it becomes invalid. This optimization works because we only care about finding windows larger than what we've already found.

Time Complexity: O(n) where n is the length of the string, as each character is visited at most twice.

Space Complexity: O(1) as the counter stores at most 26 uppercase English letters.

Example Walkthrough

Let's walk through the algorithm with s = "AABABBA" and k = 1.

Initial State:

• cnt = {}, l = 0, mx = 0

Step 1: r = 0, c = 'A'

• Add 'A': cnt = {'A': 1}, mx = 1
• Window = "A" (size 1)
• Check validity: 1 - 1 = 0 ≤ 1 ✓ Valid
• Keep window

Step 2: r = 1, c = 'A'

• Add 'A': cnt = {'A': 2}, mx = 2
• Window = "AA" (size 2)
• Check validity: 2 - 2 = 0 ≤ 1 ✓ Valid
• Keep window

Step 3: r = 2, c = 'B'

• Add 'B': cnt = {'A': 2, 'B': 1}, mx = 2
• Window = "AAB" (size 3)
• Check validity: 3 - 2 = 1 ≤ 1 ✓ Valid
• Keep window

Step 4: r = 3, c = 'A'

• Add 'A': cnt = {'A': 3, 'B': 1}, mx = 3
• Window = "AABA" (size 4)
• Check validity: 4 - 3 = 1 ≤ 1 ✓ Valid
• Keep window

Step 5: r = 4, c = 'B'

• Add 'B': cnt = {'A': 3, 'B': 2}, mx = 3
• Window = "AABAB" (size 5)
• Check validity: 5 - 3 = 2 > 1 ✗ Invalid
• Shrink: Remove s[0]='A': cnt = {'A': 2, 'B': 2}
• Move left: l = 1
• New window = "ABAB" (size 4)

Step 6: r = 5, c = 'B'

• Add 'B': cnt = {'A': 2, 'B': 3}, mx = 3
• Window = "ABABB" (size 5)
• Check validity: 5 - 3 = 2 > 1 ✗ Invalid
• Shrink: Remove s[1]='A': cnt = {'A': 1, 'B': 3}
• Move left: l = 2
• New window = "BABB" (size 4)

Step 7: r = 6, c = 'A'

• Add 'A': cnt = {'A': 2, 'B': 3}, mx = 3
• Window = "BABBA" (size 5)
• Check validity: 5 - 3 = 2 > 1 ✗ Invalid
• Shrink: Remove s[2]='B': cnt = {'A': 2, 'B': 2}
• Move left: l = 3
• New window = "ABBA" (size 4)

Final Result:

• l = 3, string length = 7
• Answer = 7 - 3 = 4

The maximum length substring is 4. We can verify this: "AABA" (replace one B with A) or "ABBA" (replace one A with B) both give us 4 consecutive same characters with exactly 1 replacement.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s. The algorithm uses a sliding window approach with a single pass through the string. Each character is visited at most twice - once when the right pointer r moves forward (in the for loop), and potentially once when the left pointer l moves forward (in the if condition). The operations inside the loop (dictionary updates, max calculation, arithmetic operations) all take O(1) time.

Space Complexity: O(|Σ|), where |Σ| is the size of the character set. The Counter object cnt stores the frequency of characters in the current window. In the worst case, it will store all unique characters that appear in the string. Since the problem deals with uppercase English letters, |Σ| = 26, making the space complexity effectively O(26) = O(1) constant space.

Common Pitfalls

Pitfall 1: Incorrectly Updating max_freq When Shrinking Window

The Problem: A common mistake is trying to recalculate max_freq accurately when shrinking the window. Developers often think they need to maintain the exact maximum frequency in the current window at all times:

# INCORRECT approach - trying to maintain exact max_freq
if right - left + 1 - max_freq > k:
    char_count[s[left]] -= 1
    if char_count[s[left]] == 0:
        del char_count[s[left]]
    left += 1
    # Recalculating max_freq - UNNECESSARY and INEFFICIENT!
    max_freq = max(char_count.values()) if char_count else 0

Why This is Wrong:

• This adds unnecessary O(26) operations for each shrink, potentially making the algorithm O(26n)
• The algorithm actually doesn't require the exact max_freq of the current window
• The "stale" max_freq value helps maintain the maximum window size found so far

The Solution: Keep max_freq as is - it represents the maximum frequency ever seen, not necessarily in the current window. This works because:

• We only care about windows larger than what we've found
• A stale (potentially larger) max_freq prevents the window from growing beyond the best size we've seen
• The window naturally slides forward maintaining the maximum valid size

Pitfall 2: Shrinking Window Too Aggressively

The Problem: Some implementations try to shrink the window until it becomes valid again:

# INCORRECT - shrinking until valid
while right - left + 1 - max_freq > k:
    char_count[s[left]] -= 1
    left += 1

Why This is Wrong:

• This can shrink the window smaller than necessary
• We lose the optimization of maintaining the maximum window size
• The algorithm becomes less efficient and harder to reason about

The Solution: Only shrink by exactly one position when the window becomes invalid. This maintains the invariant that the window size represents the maximum valid window found so far:

# CORRECT - shrink by exactly one
if right - left + 1 - max_freq > k:
    char_count[s[left]] -= 1
    left += 1

Pitfall 3: Misunderstanding the Return Value

The Problem: Developers sometimes track the maximum window size explicitly:

# UNNECESSARY complexity
max_length = 0
for right, char in enumerate(s):
    # ... window operations ...
    max_length = max(max_length, right - left + 1)
return max_length

Why This is Suboptimal:

• Adds unnecessary variable and update operations
• Makes the code more complex than needed

The Solution: Since the window only shrinks by one when it would exceed the maximum valid size, len(s) - left gives us the answer directly. The final position of left naturally tracks how much we've had to shrink from the full string length.