424. Longest Repeating Character Replacement

📝 Problem Details

• Title: 424. Longest Repeating Character Replacement
• Link: https://leetcode.com/problems/longest-repeating-character-replacement/
• Difficulty: Medium
• Tags/Categories: Sliding-Window Hashmap

input string s input integer k you can choose any character from s 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

💡 Explanation of Solution

Sliding Window Approach:
1. expand the right pointer while keeping track of:
	- frequency of each character in the current window 
	- the most frequent character count (maxFreq)

2. check the validity of the window
	- the number of non-dominant characters in the window is :
		- windowSize - maxFreq
	- if this count exceeds k, the window is invalid, so shrink it by moving left forward

3. update maxLength whenever we find a valid window 

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxFreq = 0;
        int maxLength = 0;
 
        int left = 0;
        unordered_map<char, int> map;
 
        for(int right = 0; right < s.size(); right++) {
            map[s[right]]++;
 
            // track the most frequent character in the window 
            maxFreq = max(maxFreq, map[s[right]]);
 
            int windowSize = right - left + 1;
 
            if(windowSize - maxFreq > k) {
                map[s[left]]--;
                left++;
            }
 
            maxLength = max(maxLength, right-left+1);
 
        }
 
        return maxLength;
    }
};