# Sliding window
###### tags: `Algorithm`

## 424. Longest Repeating Character Replacement

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # space complexity O(1)
        char_dict = {}
        lptr = 0
        max_len = 0
        for rptr in range(len(s)):
            # get(s[right], 0)
            if s[rptr] not in char_dict.keys():
                char_dict[s[rptr]] = 0
            char_dict[s[rptr]] += 1
            # •	✅ max_freq = most count in the current window
	        # •	❌ It doesn’t have to be a true majority element (doesn’t need >50%)
            majority = max(char_dict.values())
            window_len = rptr-lptr+1
            dif_num = window_len - majority
            while dif_num > k:
                if lptr < rptr:
                    char_dict[s[lptr]] -= 1
                    lptr += 1
                    # majority = max(char_dict.values())
                    window_len = rptr-lptr+1
                    dif_num = window_len - majority
            
            cur_len = rptr-lptr+1
            if max_len < cur_len:
                max_len = cur_len
                
        return max_len
        """
        count = {}
        left = 0
        max_freq = 0
        res = 0

        for right in range(len(s)):
            # Add s[right] to window
            count[s[right]] = count.get(s[right], 0) + 1
            max_freq = max(max_freq, count[s[right]])

            # If more than k replacements needed -> shrink window
            while (right - left + 1) - max_freq > k:
                count[s[left]] -= 1
                left += 1

            # Update result
            res = max(res, right - left + 1)

        return res
        """
                
                
            
        '''
        AABABBA
        iteration: A A B/C A B B A
        lpointer:  0 0 0 0 0 2 2 4
        rpointer:  0 1 2   3 4 5 6
        replacement count:0 0 0<1->1 1 1==1->0
        substring=[A] [A, A] [A, A, B] [A, A, B, A] [A, A, B, A, B]->[B, A, B] [B, A, B, B] [B, A, B, B, A]->[B,B,A]
        chr_table{num_A:, num_B:, ..., num_Z:}
        
        majority = max(chr_table.values())
        window_len = rpointer-lpointer
        dif_num = windwo_len - majority
        while dif_num > k:
            lpointer += 1
        
        hint
        1. verify the window, if window doesn't fit in the condition, move pointer L until it fit.
        2. find the majority element in the window
        '''

* Tutorial:
https://blog.techbridge.cc/2019/09/28/leetcode-pattern-sliding-window/