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

        n = len(prices)

        # 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 < n:

            # 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

    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        # Prefix Sum + Hashmap (Optimal)
        
        # Idea:
        #   - Let prefix[i] = sum of nums[0..i-1]
        #   - For subarray sum = goal, we need:
        #       prefix[j+1] - prefix[i] = goal  →  prefix[i] = prefix[j+1] - goal
        #   - Use hashmap to count occurrences of prefix sums efficiently.
        
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(n)

        count = defaultdict(int)  # maps prefix_sum -> number of occurrences
        count[0] = 1              # base case: sum of 0 occurs once
        prefix_sum = 0
        res = 0

        for num in nums:

            # Update current prefix sum
            prefix_sum += num

            # Check if there is a prefix that satisfies current subarray sum == goal
            if prefix_sum - goal in count:
                res += count[prefix_sum - goal]

            # Record current prefix sum occurrence
            count[prefix_sum] += 1

        return res

    def balancedString(self, s: str) -> int:
        
        # Sliding Window + Two Pointers
    
        n = len(s)
        target = n // 4
        count = Counter(s)
        
        # Only keep excess counts; ignore characters already <= target
        excess = {c: max(0, count[c] - target) for c in "QWER"}
        
        # If no excess, string is already balanced
        if all(v == 0 for v in excess.values()):
            return 0

        res = n
        left = 0

        for right in range(n):
            # Decrease count of current character in window
            if s[right] in excess:
                excess[s[right]] -= 1

            # Shrink window while it covers all excess characters
            while all(v <= 0 for v in excess.values()):
                res = min(res, right - left + 1)
                if s[left] in excess:
                    excess[s[left]] += 1
                left += 1

        return res

    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        
        # Sliding Window + Two Pointers
        
        # Idea:
        #   - Maintain a window [left, right] where total cost <= maxCost.
        #   - Expand right pointer; shrink left when cost exceeds maxCost.
        #   - Track maximum window length.
        #
        # Rules:
        #   1. Compute cost[i] = abs(ord(s[i]) - ord(t[i])).
        #   2. Expand right, accumulate total_cost.
        #   3. While total_cost > maxCost, shrink window from left.
        #   4. Update maximum valid window length.
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(1)

        n = len(s)
        left = 0
        total_cost = 0
        max_len = 0

        for right in range(n):
            # Cost to change s[right] to t[right]
            cost = abs(ord(s[right]) - ord(t[right]))
            total_cost += cost

            # Shrink window if cost exceeds maxCost
            while total_cost > maxCost:
                total_cost -= abs(ord(s[left]) - ord(t[left]))
                left += 1

            # Update maximum length of valid substring
            max_len = max(max_len, right - left + 1)

        return max_len

    from collections import defaultdict

    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        
        # Sliding Window + Hashmap
        
        # Idea:
        #   - Number of subarrays with exactly K distinct elements:
        #       = atMostK(nums, K) - atMostK(nums, K-1)
        #   - Use sliding window to count at most K distinct integers.
        #
        # Rules:
        #   1. Maintain a window with <= K distinct numbers.
        #   2. Expand right; shrink left if distinct count > K.
        #   3. For each right, add (right - left + 1) to count.
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(n)

        def atMostK(nums, K):
            count = defaultdict(int)
            left = 0
            res = 0
            distinct = 0

            for right in range(len(nums)):
                if count[nums[right]] == 0:
                    distinct += 1
                count[nums[right]] += 1

                # Shrink window while distinct > K
                while distinct > K:
                    count[nums[left]] -= 1
                    if count[nums[left]] == 0:
                        distinct -= 1
                    left += 1

                # Add number of subarrays ending at right
                res += right - left + 1

            return res

        # Exactly K distinct = at most K - at most K-1
        return atMostK(nums, k) - atMostK(nums, k-1)

    def totalFruit(self, fruits: List[int]) -> int:
        # Sliding Window + Hashmap
            # Idea:
        #   - Use a sliding window to maintain at most 2 distinct fruit types.
        #   - Expand right; shrink left when more than 2 distinct types appear.
        #   - Track maximum window length.
        #
        # Rules:
        #   1. Maintain a hashmap: fruit type -> count in current window.
        #   2. Expand right pointer, increment count.
        #   3. If distinct fruits > 2, shrink window from left until <= 2.
        #   4. Update maximum length for each right.
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(1) (at most 2 types in hashmap)

        count = defaultdict(int)
        left = 0
        max_len = 0

        for right in range(len(fruits)):
            # Include current fruit in window
            count[fruits[right]] += 1

            # Shrink window while more than 2 distinct fruits
            while len(count) > 2:
                count[fruits[left]] -= 1
                if count[fruits[left]] == 0:
                    del count[fruits[left]]
                left += 1

            # Update maximum number of fruits collected
            max_len = max(max_len, right - left + 1)

        return max_len

    def longestSubarray(self, nums: List[int], limit: int) -> int:
        # Sliding Window + Monotonic Deques
    
        # Idea:
        #   - Maintain two deques:
        #       max_d: decreasing deque for maximum
        #       min_d: increasing deque for minimum
        #   - Expand right pointer; shrink left if max - min > limit.
        #   - Track maximum window length.
        #
        # Rules:
        #   1. Append nums[right] to both deques, maintaining monotonicity.
        #   2. While current window violates limit (max - min > limit), shrink from left.
        #   3. Update maximum window length.
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(n) (for deques)

        max_d = deque()  # stores elements in decreasing order
        min_d = deque()  # stores elements in increasing order
        left = 0
        max_len = 0

        for right, num in enumerate(nums):
            # Maintain decreasing max deque
            while max_d and num > max_d[-1]:
                max_d.pop()
            max_d.append(num)

            # Maintain increasing min deque
            while min_d and num < min_d[-1]:
                min_d.pop()
            min_d.append(num)

            # Shrink window if difference exceeds limit
            while max_d[0] - min_d[0] > limit:
                if nums[left] == max_d[0]:
                    max_d.popleft()
                if nums[left] == min_d[0]:
                    min_d.popleft()
                left += 1

            # Update maximum window length
            max_len = max(max_len, right - left + 1)

        return max_len

    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # Sliding Window + Two Pointers
    
        # Idea:
        #   - Maintain a window [left, right] with sum >= target.
        #   - Expand right pointer to increase sum.
        #   - Shrink left pointer while sum >= target to find minimal length.
        #
        # Rules:
        #   1. Keep track of current window sum.
        #   2. Expand right, add nums[right] to sum.
        #   3. While sum >= target, shrink left and update minimal length.
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(1)

        left = 0
        curr_sum = 0
        min_len = float('inf')

        for right in range(len(nums)):
            # Include current number in window
            curr_sum += nums[right]

            # Shrink window from left while sum >= target
            while curr_sum >= target:
                min_len = min(min_len, right - left + 1)
                curr_sum -= nums[left]
                left += 1

        # If min_len unchanged, no valid subarray
        return 0 if min_len == float('inf') else min_len

    def numberOfSubstrings(self, s: str) -> int:
        # Sliding Window + Hashmap
    
        # Idea:
        #   - Maintain a window [left, right] containing at least one 'a', 'b', 'c'.
        #   - For each right, the number of valid substrings ending at right
        #     = left + 1 (number of starting indices for current window).
        #
        # Rules:
        #   1. Use hashmap to count characters in the window.
        #   2. Expand right pointer and include s[right].
        #   3. Shrink left while window still contains all three characters.
        #   4. Add (left) to result for each right.
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(1) (at most 3 characters in hashmap)

        count = defaultdict(int)
        left = 0
        res = 0

        for right in range(len(s)):
            # Include current character
            count[s[right]] += 1

            # Shrink window from left while it still contains all three characters
            while all(count[c] > 0 for c in "abc"):
                count[s[left]] -= 1
                left += 1

            # Add number of valid substrings ending at right
            res += left

        return res

    def longestOnes(self, nums: List[int], k: int) -> int:
        # Sliding Window + Two Pointers
    
        # Idea:
        #   - Maintain a window [left, right] with at most k zeros.
        #   - Expand right; shrink left when number of zeros > k.
        #   - Track maximum window length.
        #
        # Rules:
        #   1. Count zeros in current window.
        #   2. Expand right pointer, increment zeros if nums[right] == 0.
        #   3. While zeros > k, shrink window from left.
        #   4. Update maximum window length.
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(1)

        left = 0
        max_len = 0
        zeros = 0

        for right in range(len(nums)):
            # Include current element
            if nums[right] == 0:
                zeros += 1

            # Shrink window if zeros exceed k
            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1

            # Update maximum length
            max_len = max(max_len, right - left + 1)

        return max_len

    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # Sliding Window + Prefix Count of Odds
    
        # Idea:
        #   - Convert nums to 0 (even) / 1 (odd)
        #   - Use atMostK helper to count subarrays with ≤ k odd numbers.
        #   - Exactly k odd numbers = atMostK(k) - atMostK(k-1)
        #
        # Rules:
        #   1. Maintain sliding window with ≤ K odd numbers.
        #   2. Expand right; shrink left if number of odd numbers > K.
        #   3. Count subarrays ending at right.
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(1)

        def atMost(k):
            left = 0
            res = 0
            odd_count = 0

            for right in range(len(nums)):
                if nums[right] % 2 == 1:
                    odd_count += 1

                # Shrink window if odd_count > k
                while odd_count > k:
                    if nums[left] % 2 == 1:
                        odd_count -= 1
                    left += 1

                # Number of subarrays ending at right with ≤ k odd numbers
                res += right - left + 1

            return res

        return atMost(k) - atMost(k-1)

    def shortestSubarray(self, nums: List[int], k: int) -> int:
        
        # Sliding Window + Prefix Sum + Monotonic Queue
        
        # Idea:
        #   - Compute prefix sums: P[i] = sum(nums[:i])
        #   - We want shortest j-i with P[j] - P[i] >= k
        #   - Maintain a deque of indices with increasing prefix sums
        #   - Pop from front when we find a valid subarray
        #
        # Rules:
        #   1. Compute prefix sums.
        #   2. Use deque to store indices of increasing prefix sums.
        #   3. For current prefix sum P[j], pop from deque front if P[j] - P[deque[0]] >= k
        #   4. Maintain deque monotonic by popping back if P[j] <= P[deque[-1]]
        #   5. Track minimum window length.
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(n)

        n = len(nums)
        P = [0] * (n + 1)  # prefix sum
        for i in range(n):
            P[i + 1] = P[i] + nums[i]

        res = n + 1
        dq = deque()  # stores indices of prefix sums

        for i in range(n + 1):
            # Check if current prefix - smallest prefix >= k
            while dq and P[i] - P[dq[0]] >= k:
                res = min(res, i - dq.popleft())

            # Maintain deque increasing
            while dq and P[i] <= P[dq[-1]]:
                dq.pop()

            dq.append(i)

        return res if res <= n else -1