LeetCode: Sliding Window

    def maxSumSubarray(nums, k):
        window_sum = sum(nums[:k])
        max_sum = window_sum
        
        for i in range(k, len(nums)):
            window_sum += nums[i] - nums[i - k]
            max_sum = max(max_sum, window_sum)
        
        return max_sum

    # maxSumSubarray([1, 4, 2, 10, 2, 3, 1, 0, 20], 4) = 24

    def lengthOfLongestSubstring(s: str) -> int:
        char_index = {}
        left = max_len = 0
        
        for right in range(len(s)):
            if s[right] in char_index and char_index[s[right]] >= left:
                left = char_index[s[right]] + 1
            
            char_index[s[right]] = right
            max_len = max(max_len, right - left + 1)
        
        return max_len

    # "abcabcbb" → lengthOfLongestSubstring = 3

    def maxProfit(self, prices: List[int]) -> int:

        # Note:
        # Variable Size Sliding Window => [left, right]
        # 1. left points to day we buy (lowest price so far)
        # 2. right scans forward best profit day (highest sell price -> highest profit)
        # 3. Get profit:
        #    if prices[left] < prices[right]: profit possible, update max_profit
        #    if prices[left] > prices[right]: lower buy found, update left
        # Result: finds lowest buy and highest profit

        # Lowest buy price day index, curr sell price day index
        left, right = 0, 1

        # max profit so far
        max_profit = 0

        # time complexity: iterate over list of n days
        while right < len(prices):

            # curr day higher than min
            if prices[left] < prices[right]:
                
                # calculate possible profit, update max_profit
                profit = prices[right] - prices[left]
                max_profit = max(max_profit, profit)

            # curr day lower than min
            else:
                left = right

            # iterate curr day
            right += 1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return max_profit

    def maxProfit(self, prices: List[int]) -> int:
        
        # Note:
        # Variable Size Sliding Window => [left, right]
        # 1. left points to day we buy (lowest price so far)
        # 2. right scans forward for best profit day (highest sell price -> highest profit)
        # 3. Get profit:
        #    if prices[left] < prices[right]: profit possible, update max_profit
        #    if prices[left] > prices[right]: lower buy found, update left
        # Result: finds lowest buy and highest profit
        
        # Lowest Buy Day so far (+inf)
        left = float('inf')
        
        # max profit so far
        max_profit = 0

        # time complexity: iterate over list of n prices O(n)
        for right in prices:

            # profit possible
            if left < right:
                profit = right - left
                max_profit = max(max_profit, profit)

            # new min buy day found
            else:
                left = right

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return max_profit

    def maxProfit(self, prices: List[int]) -> int:

        # Note:
        # 1. DP[i][0] = highest profit so far
        #    DP[i][1] = lowest buy price so far
        # 2. At each day update [0] and [1]:
        #    [0] = max(highest profit so far, profit from using lowest buy price so far against today sell price)
        #    [1] = min(lowest buy price so far, todays buy price)
    
        # Empty check
        if not prices:
            return 0

        n = len(prices)

        # 2D array of n rows with 2 columns
        # [i][0] -> max profit at day i
        # [i][1] -> min buying price at day i
        dp = [[0]*2 for _ in range(n)]

        # set up dynamic programming table first iteration:

        # min price up to day 0
        dp[0][0] = -prices[0]
        # max profit up to day 0
        dp[0][1] = 0


        # time complexity: iterate across n days for prices O(n)
        for i in range(1, n):

            # update min price
            dp[i][0] = max(dp[i-1][0], -prices[i])            
            # update max profit
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])


        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return dp[-1][1]

    def maxProfit(self, prices: List[int]) -> int:

        # Note:
        # 1.  Compress DP O(n) table to O(1)
        #     min_price = min price up to day i
        #     max_profit = max profit up to day i
        # # 2. At each day update min and max:
        #     min_price = min(lowest price so far vs todays buy price)
        #     max_profit = max(highest profit so far vs profit from todays sell price - lowest buy price)
        # Result: Max profit at day n

        n = len(prices)

        # set up compressed dynamic programming table first iteration:        
        # [i][0] -> min buying price up to day i
        # [i][1] -> max profit up to day i

        # min price up to day 0
        min_price = -prices[0]
        # max profit up to day 0
        max_profit = 0


        # time complexity: iterate over n day prices O(n)
        for i in range(1, n):
            
            # update compressed dp table, (for up to day i)
          
            # update min price
            min_price = max(min_price, -prices[i])
            # update max profit
            max_profit = max(max_profit, min_price + prices[i])  

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return max_profit

    def lengthOfLongestSubstring(self, s: str) -> int:

        # Note:
        # Variable Sliding Window => [left, right]
        # Hashmap => char -> most recent index
        # 1. move right pointer forward while no duplicates, 
        # 2. If duplicate found, move left to index after oldest duplicate
        # 3. Update max length after processing each character.
        # Result: max length without repeating characters

        # char -> most recent index
        char_MRI = {} 

        # Variable Sliding window: [left, right]
        left = 0

        # max length
        max_len = 0

        # time complexity: iterate over string n length O(n)
        for right, new_char in enumerate(s):

            # check if char already found and within curr window
            if new_char in char_MRI and left <= char_MRI[new_char]:
                
                # duplicate exists, move left -> oldest index + 1
                left = char_MRI[new_char] + 1
            
            # update most recent index for curr char
            char_MRI[new_char] = right

            # get new length
            new_length = right - left + 1

            # update string length
            max_len = max(max_len, new_length)
        
        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return max_len

    def lengthOfLongestSubstring(self, s: str) -> int:

        # Note:
        # Variable Sliding Window => [left, right]
        # Hashmap => char -> most recent index
        # 1. move right pointer forward while no duplicates, 
        # 2. If duplicate found, move left to index after oldest duplicate
        # 3. Update max length after processing each character.
        # Result: max length without repeating characters

        # char -> most recent index
        char_MRI = {} 

        # Variable Sliding window: [left, right]
        left = 0

        # max length
        max_len = 0

        # total prices
        n = len(s)

        # time complexity: iterate over string n length O(n)
        for right in range(n):

            new_char = s[right]

            # check if new_char already found
            if new_char in char_MRI:

                # check if new_char within current window
                if left <= char_MRI[new_char]:
                
                    # duplicate found,
                    # move left: oldest index + 1
                    left = char_MRI[new_char] + 1
            
            # update most recent index for curr new_char
            char_MRI[new_char] = right
            new_length = right - left + 1

            # update string length
            max_len = max(max_len, new_length)
        
        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return max_len

    def characterReplacement(self, s: str, k: int) -> int:
        
        # Note:
        # Variable Sliding Window => [left, right]
        # Hashmap => char -> count

        # Note:
        # Idea: extend window via right,
        # keep count of chars within the window,
        # keep count of highest count char within window,
        # shrink the window via left shift.

        # needed replacements:
        # (window size - count of most frequent char within window),
        # is higher than available replacements: k
        # then we shrink the window from the left.

        # char -> count
        count = defaultdict(int)

        # max_freq: max count across all chars in count hashmap
        max_freq = 0  

        # Variable Sliding window: [left, right]
        left = 0

        # max length
        max_len = 0

        # time complexity: iterate right pointer over string n length O(n)
        for right in range(len(s)):

            # intake new char, increase count
            count[s[right]] = count.get(s[right], 0) + 1

            # update max_freq
            max_freq = max(max_freq, count[s[right]])

            # check if window shrink required:
            # needed replacements > available replacements
            if (right - left + 1) - max_freq > k:

                # decrease char count and shrink window
                count[s[left]] -= 1
                left += 1  

            # update max_len
            max_len = max(max_len, right - left + 1)

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return max_len

    def checkInclusion(s1: str, s2: str) -> bool:

        # Note:
        # Fixed Sliding Window => [left, right] of len (s1)

        # Note:
        # 1. Track char count in s1 and sliding window
        # 2. right extends to fit len(s1)
        # 3. shift left and right to fit len(s1)
        # 4. If char count match, permutation exist

        # s1 len > s2 len: permutation not possible
        len_s1, len_s2 = len(s1), len(s2)
        if len_s1 > len_s2:
            return False

        # s1 char count
        freq_s1 = {}
        for ch in s1:
            freq_s1[ch] = freq_s1.get(ch, 0) + 1

        # sliding window char count
        window_freq = {}
        
        # Fixed sliding window [left, right]
        left = 0

        # time complexity: iterate right over string s2 n length O(n)
        for right in range(len_s2):

            # extend sliding window, update char count
            window_freq[s2[right]] = window_freq.get(s2[right], 0) + 1

            # reduce sliding window if size > s1
            if right - left + 1 > len_s1:

                # decrease char count and shift left
                left_char = s2[left]
                window_freq[left_char] -= 1

                # remove if frequency reaches 0
                if window_freq[left_char] == 0:
                    del window_freq[left_char]

                # iterate left pointer
                left += 1

            # counts match, permutation exists
            if window_freq == freq_s1:
                return True

        # no permutation found

        # overall: time complexity O(n) 
        # overall: space complexity O(n)
        return False

    def checkInclusion(s1: str, s2: str) -> bool:
        
        # Note:
        # 1. Fixed sliding window of len(s1)
        # 2. Two Count arrays size 26 for s1 and window
        # 3. Track chars arrays between arrays that match with count
        # 4. Window slides:
        #    Add new char and update matches
        #    Remove old char and updates matches
        # 5. If matches == 26, permutation s1 exists in window and s2
        # Results: validate if permutation of s1 exists in s2

        # s1 len > s2 len: permutation not possible
        len_s1, len_s2 = len(s1), len(s2)
        if len_s1 > len_s2:
            return False

        # s1 and window counts
        freq_s1 = [0] * 26
        freq_window = [0] * 26

        # char count for s1
        for ch in s1:
            freq_s1[ord(ch) - ord('a')] += 1
        
        # char count for first window in s2
        for ch in s2[:len_s1]:
            freq_window[ord(ch) - ord('a')] += 1

        # Matches: 
        # number of positions between s1 and window counts where count matches
        matches = sum(1 for i in range(26) if freq_s1[i] == freq_window[i])

        # Fixed Size Window => [left, right] for len(s1)
        left = 0

        # time complexity: iterate right over list of n length O(n)
        for right in range(len_s1, len_s2):
            
            # if count arrays match between s1 and window: permutation exists
            if matches == 26:
                return True

            # Add new char to window
            index_add = ord(s2[right]) - ord('a')
            freq_window[index_add] += 1

            # update matches for added char
            if freq_window[index_add] == freq_s1[index_add]:
                matches += 1
            elif freq_window[index_add] == freq_s1[index_add] + 1:
                matches -= 1

            # Remove char going out of window
            index_remove = ord(s2[left]) - ord('a')
            freq_window[index_remove] -= 1

            # update matches for removed char
            if freq_window[index_remove] == freq_s1[index_remove]:
                matches += 1
            elif freq_window[index_remove] == freq_s1[index_remove] - 1:
                matches -= 1
            left += 1

        # overall: time complexity 
        # overall: space complexity 
        return matches == 26

    def checkInclusion(self, s1: str, s2: str) -> bool:

        # Note:
        # 1. Uses two hashmaps:
        # 2. Expands right pointer until all required chars are included
        # 3. Shifts left pointer to shrink window while maintaining validity
        # 4. Tracks smallest valid window found so far
        # Result: returns smallest substring containing all chars of t or ""

        # t len > s len: substring not possible
        if len(t) > len(s):
            return ""

        # t char count
        target_freq = defaultdict(int)
        for char in t:
            target_freq[char] += 1

        # sliding window char count
        window_freq = defaultdict(int)

        # Number of unique chars from t needed  
        need = len(target_freq)     

        # Number of chars from t that meet the required count
        have = 0                          

        # min substring
        min_len = float("inf")

        # Variable Sliding Window => [left, right]
        left = 0

        # 
        res_start = 0

        # time complexity: iterate right over list s of n length O(n)
        for right in range(len(s)):

            # extending window, update char count
            char = s[right]
            window_freq[char] += 1

            # Check if this character satisfies the required t frequency
            if char in target_freq and window_freq[char] == target_freq[char]:
                have += 1

            # shrink window while frequencies are valid
            while have == need:
                
                # curr window
                window_len = right - left + 1
                
                # update min length, mark start of min window
                if window_len < min_len:
                    min_len = window_len
                    res_start = left

                # reduce char count and shrink window
                left_char = s[left]
                window_freq[left_char] -= 1
                
                # check if frequencies are valid
                if left_char in target_freq and window_freq[left_char] < target_freq[left_char]:
                    have -= 1

                # iterate
                left += 1

        # if at least one valid sub string exists, return
        if min_len != float("inf"):
            res = s[res_start:res_start + min_len]

        # no sub string found, return ""
        else: 
            res = ""

        # overall: time complexity
        # overall: space complexity
        return res

    def minWindow(self, s1: str, s2: str) -> bool:

        # Note:
        # 1. Single hashmap to track remaining required chars
        # 2. Expands right pointer while decreasing count of matched chars
        # 3. When all chars matches, contracts left pointer
        # 4. Tracks smallest window
        # 5. Returns smallest substring containing all chars of t (or "" if none)

        # t len > s len: substring not possible
        if len(s) < len(t):
            return ""

        # t char count
        char_count = defaultdict(int)
        for ch in t:
            char_count[ch] += 1

        # Total num of characters (with duplicates) still needed
        target_chars_remaining = len(t)         

        # (start_index, end_index)
        min_window = (0, float("inf"))          

        # Left pointer
        start_index = 0                         

        # time complexity: iterate right over s2 of n length O(n)
        for end_index, ch in enumerate(s):

            # Expand right
            if char_count[ch] > 0:
                # One needed character matched
                target_chars_remaining -= 1     

            # Always decrement (can go negative)
            char_count[ch] -= 1                 

            # Once we have matched all characters
            if target_chars_remaining == 0:
                # Shrink from left as much as possible
                while True:
                    char_at_start = s[start_index]
                    if char_count[char_at_start] == 0:
                        break                   # Cannot remove this char without breaking
                    char_count[char_at_start] += 1
                    start_index += 1

                # Check if current window is smaller
                if end_index - start_index < min_window[1] - min_window[0]:
                    min_window = (start_index, end_index)

                # Shrink window by 1 to move forward
                char_count[s[start_index]] += 1
                target_chars_remaining += 1
                start_index += 1

        # Extract window if found
        if min_window[1] > len(s):
            res = ""
        else: 
            res = s[min_window[0]:min_window[1]+1]


        # overall: time complexity
        # overall: space complexity
        return res

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        # Note:
        # 1. Use a max heap (negative value min heap), to keep track of
        #    potential max values in the current window
        # 2. Each heap entry is (-value, index) so max is at top
        # 3. Before taking max from heap, pop all elements that are outside of 
        #    of the current window (index <= i - k)
        # 4. Append the top of the heap (largest value) to the result for each window

        # Empty check
        if not nums or k == 0:
            return []

        # list of max values for each window
        result = []

        # max heap (min heap with negative values)
        # (-value, index)
        heap = []  

        # Initialize the first window:
        # push all elements to the max heap
        for i in range(k):
            heapq.heappush(heap, (-nums[i], i))

        # append curr window max to result list, after k values added to queue
        peek_max = -heap[0][0]
        result.append(peek_max)

        # time complexity: iterate over list of n length O(n)
        for i in range(k, len(nums)):

            # Push new element: (-value, index)
            heapq.heappush(heap, (-nums[i], i))

            # we only care about elements affecting the current max
            # so we pop the top of the heap,
            # while elements are out of the current window range
            while heap[0][1] <= i - k:
                # removes top stale element
                heapq.heappop(heap)

            # max is guaranteed to be within current window range
            # append curr window max to result list
            peek_max = -heap[0][0]
            result.append(peek_max)

        # overall: time complexity O(n log k)
        # overall: space complexity O(k)
        return result

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        # Note:
        # 1. Use a dequeue to store elements in decreasing order to track max
        # 2. Maintain the dequeue such that front has max element for current window
        # 3. When sliding the window:
        #    Remove elements smaller than incoming element from back of dequeue
        #    Remove outgoing element from the front if it equals element leaving the window
        # 4. Append the front element of the dequeue (curr max) to results after each slide

        # Empty check
        if not nums or k == 0:
            return []

        res = []

        # stores elements in decreasing order
        dq = deque([])

        # put k element in the dequeue and make sure the max is at the front
        for i in range(k):
            while (dq and nums[i] > dq[-1]):
                dq.pop()
            dq.append(nums[i])

        # append current max for first window
        res.append(dq[0])

        # slide window from k to end
        for i in range(k, len(nums)):

            # remove element leaving the window from front if it matches
            if (nums[i - k] == dq[0]):
                dq.popleft()

            # 
            while (dq and nums[i] > dq[-1]):
                dq.pop()

            # append new elem max
            dq.append(nums[i])
            
            # append current max
            res.append(dq[0])

        # overall: time complexity
        # overall: space complexity
        return res

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        # Note:
        # 1. Precompute max in fixed-size blocks:
        #    - left_max[i]: max from block start to i
        #    - right_max[i]: max from block end to i (scanned backwards)
        # 2. For window starting at i, max = max(right_max[i], left_max[i+k-1])
        #    - right_max[i] covers block starting at i
        #    - left_max[i+k-1] covers block ending at i+k-1
        # 3. Eliminates need for deque by reusing block maxima

        n = len(nums)
        if not nums or k == 0:
            return []

        left_max = [0] * n
        right_max = [0] * n

        # Fill left_max: scanning forward
        for i in range(n):
            if i % k == 0:
                left_max[i] = nums[i]  # Block start
            else:
                left_max[i] = max(left_max[i-1], nums[i])

        # Fill right_max: scanning backward
        for i in range(n-1, -1, -1):
            if (i+1) % k == 0 or i == n-1:
                right_max[i] = nums[i]  # Block end
            else:
                right_max[i] = max(right_max[i+1], nums[i])

        # Compute sliding window max
        res = []
        for i in range(n-k+1):
            res.append(max(right_max[i], left_max[i+k-1]))

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res