LeetCode Solution 424 - Longest Repeating Character Replacement

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 at most k times. Find the length of the longest substring containing the same letter after performing the changes.

Example:

Input:

s = "AABABBA"
k = 1

Output:

4

Explanation:

Replace the first 'B' with 'A' to get "AAAA" or the second 'B' with 'A' to get "AABAA".

---

Optimal Approach: Sliding Window + Frequency Count

Why Sliding Window?

• Efficiently expands and contracts the window without re-evaluating the entire string.
• Maintains a frequency count to track the most frequent character in the current window.

Algorithm:

1. Maintain a sliding window with two pointers left and right.
2. Track the frequency of characters in the window using a hash map.
3. Find the most frequent character in the window and determine how many changes are needed to make all characters in the window the same.
4. If changes needed (window size - max frequency) exceed k, move the left pointer.
5. Update the maximum window length at each step.

---

C++ Code Implementation

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> freq(26, 0);
        int left = 0, right = 0, maxCount = 0, maxLength = 0;
        
        while (right < s.length()) {
            maxCount = max(maxCount, ++freq[s[right] - 'A']);
            
            if ((right - left + 1) - maxCount > k) {
                --freq[s[left] - 'A'];
                left++;
            }
            
            maxLength = max(maxLength, right - left + 1);
            right++;
        }
        return maxLength;
    }
};

---

Step-by-Step Explanation

1. Sliding Window Expansion: We expand right and update frequency of s[right].
2. Calculate Needed Replacements: If (right - left + 1) - maxCount > k, we shrink the window.
3. Window Shrinking: Increment left and update frequency count.
4. Update Maximum Length: Store the maximum window size encountered.

---

Dry Run

Input:

s = "AABABBA", k = 1

Execution:

Step	Window	Max Count	Replacements Needed	Action
1	A	1	0	Expand
2	AA	2	0	Expand
3	AAB	2	1	Expand
4	AABA	2	1	Expand
5	AABAB	2	2 (> k)	Shrink
6	ABABB	2	1	Expand
7	BABBA	2	1	Expand
8	ABBAB	2	2 (> k)	Shrink
Max Length	4

---

Alternative Approaches

Approach	Time Complexity	Space Complexity	Reason for Rejection
Brute Force (Check all substrings)	O(N^2)	O(1)	Too slow for large inputs
Sliding Window + HashMap	O(N)	O(26) → O(1)	Best balance of time and space
Sorting + Two Pointers	O(N log N)	O(N)	Sorting is unnecessary

---

Complexity Analysis

• Time Complexity: O(N) since each character is processed at most twice (once when expanding, once when contracting).
• Space Complexity: O(26) = O(1) since we store character frequencies.

---

Conclusion

• Best Approach: Sliding Window with frequency count for optimal performance.
• Further Practice:
  • Longest Substring Without Repeating Characters
  • Minimum Window Substring

This solution efficiently finds the longest repeating character substring using Sliding Window + Frequency Count, making it optimal for large inputs.