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 containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        # Sliding Window + HashSet

        # Array Representation:
        #   - Maintain a window of at most size k
        #   - Keep elements in a set representing current window
        #   - If we encounter a duplicate within the window, return True

        n = len(nums)
        if n <= 1 or k <= 0:
            return False

        # Window elements
        window = set()

        # Pointers
        left = 0
        right = 0

        # tc: iterate over n O(n)
        while right < n:

            # If duplicate in window, return True
            if nums[right] in window:
                return True

            # Add current element to window
            window.add(nums[right])

            # If window exceeds size k, remove leftmost element
            if len(window) > k:
                window.remove(nums[left])
                left += 1

            # Expand right pointer
            right += 1

        # No duplicates found within distance k
        return False

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        # Two Pointer + HashMap Representation:
        #   - Treat each element as a potential "right pointer"
        #   - Maintain a map of {value: last_seen_index} representing
        #     the "best left pointer" for that value
        #   - For each new right pointer, check if distance to last_seen_index <= k

        # Idea:
        #   - Only the most recent occurrence of a value matters
        #   - If current index - last_seen_index <= k, we have a duplicate within window
        #   - Otherwise, update last_seen_index to current index

        # HashMap storing last seen index of each value
        last_seen = {}

        # tc: iterate over n O(n)
        for right, val in enumerate(nums):

            # Check if val has been seen recently
            if val in last_seen:
                # Compute distance to last occurrence
                distance = right - last_seen[val]

                # Duplicate within allowed distance
                if distance <= k:
                    return True

            # Update last seen index to current position
            last_seen[val] = right

        # No duplicates found within distance k
        return False

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

        # Two Pointer Sliding Window (Variable Size)

        # Stock Representation:
        #   - Treat each day as a potential sell day
        #   - Maintain a window [left, right] where:
        #        left: best buy day so far (lowest price seen)
        #        right: current sell day candidate (highest prices seen)

        # Idea:
        #   - Always buy before you sell
        #   - If current price is higher than buy price, compute profit
        #   - If current price is lower than buy price, we have found better buy price, reset window

        n = len(prices)

        # Lowest buy price so far
        left = 0

        # Current sell price so far
        right = 0

        # Max profit so far
        maxProfit = 0

        # tc: iterate over n O(n)
        while right < n:

            buyPrice = prices[left]
            sellPrice = prices[right]

            # If there is profit to be made
            if buyPrice < sellPrice:
                
                # Calculate profit
                profit = sellPrice - buyPrice

                # Compare profit
                maxProfit = max(maxProfit, profit)

            # There is a better buy price found
            else:
                left = right

            # Check next day
            right += 1

        # overall: tc O(n)
        # overall: sc O(1)
        return maxProfit

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

        # Dynamic Programming (Full DP Table)

        # Stock Representation:
        #   - Treat each day as potential sell day
        #   - Maintain a state tracking where:
        #        buyPrice[i]: best buy price up to day i (lowest price seen)
        #        profit: most profit made up to day i (highest profit made using each day as a sell day)

        # Idea:
        #   - Always buy before you sell
        #   - If current price is higher than buy price, compute profit
        #   - If current price is lower than buy price, we have found better buy price, reset window

        # Empty check: no profit to be made
        if not prices:
            return 0

        n = len(prices)

        # Initialize DP table explicitly
        # dp[i][0]: best buy price up to day i (lowest price seen)
        # dp[i][1]: most profit made up to day i (highest profit made using each day as a sell day)
        # sc: O(n)
        dp = []
        
        # tc: O(n)
        for i in range(n):
            dp.append([0, 0])


        # Set up first iteration:
        # tc: O(1)
        
        # Min price up to day 0
        dp[0][0] = -prices[0]
        # Max profit up to day 0, cannot buy and sell on same day
        dp[0][1] = 0

        # tc: iterate across n days O(n)
        for i in range(1, n):

            #   - A smaller price produces a smaller negative value, 
            #     so maximizing hold is equivalent to minimizing buy price
            #     2  => -2      hold = max(hold, -price) 
            #     10 => -10       we pick the least negative value, and thus the lowest buy price
            
            dp[i][0] = max(dp[i-1][0], -prices[i])            
            
            # profit = hold + sellPrice
            #        = (-3) + 10
            #        = 7            
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])


        # overall: tc O(n)
        # overall: sc O(n)
        return dp[-1][1]

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

        # Dynamic Programming (State Compression)

        # Stock Representation:
        #   - Treat each day as potential sell day
        #   - Maintain a state tracking where:
        #        buyPrice: best buy price so far (lowest price seen)
        #        profit: most profit made so far (highest profit made using each day as a sell day)

        # Idea:
        #   - Always buy before you sell
        #   - If current price is higher than buy price, compute profit
        #   - If current price is lower than buy price, we have found better buy price, reset window

        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
        buyPrice = -prices[0]
        # max profit up to day 0
        max_profit = 0


        # tc: iterate over n days O(n)
        for i in range(1, n):
            
            #   - A smaller price produces a smaller negative value, 
            #     so maximizing hold is equivalent to minimizing buy price
            #     2  => -2      hold = max(hold, -price) 
            #     10 => -10       we pick the least negative value, and thus the lowest buy price
            
            buyPrice = max(min_price, -prices[i])

            # profit = hold + sellPrice
            #        = (-3) + 10
            #        = 7
            profit = max(max_profit, min_price + prices[i])  

        # overall: tc O(n)
        # overall: sc O(1)
        return max_profit

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

        # Sliding Window (Variable Size Window)

        # Substring Representation:
        #   - Maintain window [left, right]
        #   - Hashmap: char -> most recent index occurrence for char

        # Idea:
        #   - Expand right pointer to explore new characters
        #   - If duplicate found inside current window,
        #     move left pointer to remove previous duplicate
        #   - Check max length at every step

        # char -> most recent index occurrence for char
        charMRI = {} 

        # Sliding Window Variables
        # sc: O(1)

        # left boundary of current substring
        left = 0

        # right boundary of current substring
        right = 0

        # max length so far
        maxLen = 0

        # tc: iterate over n O(n)
        while right < n:
                
                # character we just added to substring
                newChar = s[right]

                # If duplicate exists within current window
                # tc: O(1)
                if newChar in charMRI and left <= charMRI[newChar]:

                    # Move left pointer to remove previous duplicate
                    left = charMRI[newChar] + 1

                # Update most recent index for character
                # tc: O(1)
                charMRI[newChar] = right

                # Update window length
                # tc: O(1)
                currLen = right - left + 1

                # Check max length
                maxLen = max(maxLen, currLen)

                # Expand substring
                # tc: O(1)
                right += 1

            
        # overall: tc O(n)
        # overall: sc O(1)
        return max_len

    def characterReplacement(self, s: str, k: int) -> int:
        
        # Sliding Window (Variable Size Window)

        # Substring Representation:
        #   - Maintain window [left, right]
        #   - Hashmap: char -> count within substring

        # Idea:
        #   - Expand right pointer to explore new character
        #   - maxFreq will hold the highest frequency char in substring
        #   - Window is valid if:
        #       (window size - maxFreq) <= k
        #     meaning we can replace the remaining chars to match maxFreq char
        #   - If invalid, shrink window from left
        
        # Trick:
        #   - We do NOT recompute maxFreq when shrinking
        #   - Even if maxFreq becomes stale, correctness is preserved

        n = len(s)

        # char -> count
        count = defaultdict(int)

        # Sliding Window Variables
        # sc: O(1)

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

        # left boundary of current substring
        left = 0

        # right boundary of current substring
        right = 0

        # max length so far
        maxLen = 0

        #tc: iterate over n O(n)
        while right < n:

            # Expand window: include s[right]
            # tc: O(1)
            count[s[right]] += 1

            # Update maxFreq in window
            # tc: O(1)
            max_freq = max(max_freq, count[s[right]])

            # Check: window is valid if
            #       (window size - maxFreq) <= k
            #  meaning we can replace the remaining chars to match maxFreq char
            # tc: O(1)
            if k < (right - left + 1) - max_freq:

                # Shrink window from left
                # tc: O(1)
                count[s[left]] -= 1
                left += 1  

            # Check maxLen
            maxLen = max(maxLen, right - left + 1)

            # Move right pointer forward
            # tc: O(1)
            right += 1


        # overall: tc O(n)
        # overall: sc O(1)
        return maxLen

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

        # Sliding Window (Fixed Size Window)

        # Substring Representation:
        #   - Maintain window [left, right]
        #   - Window size always equals len(s1)
        #   - Hashmap: char -> frequency

        # Idea:
        #   - Build a frequency map for s1
        #   - Expand right pointer to build window in s2
        #   - If window size exceeds len(s1), shrink from left
        #   - If window frequency == s1 frequency, permutation exists

        # Since window size is fixed, left moves whenever
        # window grows larger than lens1)

        len1 = len(s1)
        len2 = len(s2)

        # s2 < s1: permutation not possible
        # tc: O(1)
        if len2 < len1:
            return False

        # s1 Frequency
        # sc: O(1)
        targetFreq = {}

        # tc: O(n)
        for ch in s1:
            targetFreq[ch] = targetFreq.get(ch, 0) + 1

        # Substring window frequency
        # sc: O(1)
        windowFreq = {}
        
        # left boundary of current substring
        left = 0

        # right boundary of current substring
        right = 0

        # tc: iterate over n O(n)
        while right < len2:

            # Add new character to substring
            # tc: O(1)
            newCharCount = windowFreq.get(s2[right], 0) + 1

            # Update substring character count
            windowFreq[s2[right]] = newCharCount

            # If window size exceeds fixed size, shrink
            # tc: O(1)
            if len1 < (right - left + 1):

                # Remove character from substring
                losingChar = s2[left]

                # Update substring character count
                windowFreq[losingChar] -= 1

                # Remove zero frequency keys
                if windowFreq[losingChar] == 0:
                    del windowFreq[losingChar]
                
                # Shrink substring from left
                # tc: O(1)
                left += 1
            
            # Window is valid size,
            # check if permutation found
            if windowFreq == targetFreq:
                return True

            # Expand substring
            # tc: O(1)
            right += 1

        # overall: tc O(n) 
        # overall: sc O(n)
        return False

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

        # Sliding Window (Fixed Size Window)

        # Substring Representation:
        #   - Maintain window [left, right]
        #   - Hashmap: char -> frequency within substring
        #   - Two maps:
        #       targetFreq -> required counts
        #       windowFreq -> current window counts

        # Idea:
        #   - Expand right pointer to explore new character
        #   - Track how many required character are satisfied
        #   - When all required characters satisfied
        #       shrink from left to minimize window
        #   - Track smallest valid window found


        # sLen < tLen: substring not possible
        # tc: O(1)
        if len(s) < len(t):
            return ""

        # Build target frequency map
        # sc: O(1)
        targetFreq = defaultdict(int)

        # tc: O(m)
        for char in t:
            targetFreq[char] += 1

        # Sliding window frequency map
        # sc: O(1)
        windowFreq = defaultdict(int)

        # Number of unique chars required
        need = len(targetFreq)     

        # Number currently satisfied
        have = 0                 

        # Sliding Window Variables
        # sc: O(1)

        # left boundary of substring
        left = 0

        # right boundary of substring
        right = 0

        # Smallest window so far
        minLen = float("inf")
        minStart = 0

        # tc: iterate over n O(n)
        while right < len(s):

            # Expand window
            # tc: O(1)
            char = s[right]
            windowFreq[char] += 1

            # Check if requirement satisfied
            # tc: O(1)
            if (char in targetFreq and 
                windowFreq[char] == targetFreq[char]):
                have += 1


            # Shrink window while valid
            # tc: amortized O(n)
            while have == need:
                
                # Substring size
                windowLen = right - left + 1
                
                # Update minimum window
                if windowLen < minLen:
                    minLen = windowLen
                    minStart = left

                # Remove left character
                losingChar = s[left]
                windowFreq[losingChar] -= 1
                
                # If removing breaks validity
                if (losingChar in targetFreq and 
                    windowFreq[losingChar] < targetFreq[losingChar]):
                    have -= 1

                # Shrink substring from left
                # tc: O(1)
                left += 1

            # Expand substring
            # tc: O(1)
            right += 1

        # If no valid substring was found
        if minLen == float("inf"):
            return ""

        # Splice min substring
        res = s[minStart:(minStart + minLen)]

        # overall: tc O(n + m)
        # overall: sc O(1)
        return res

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

        # Sliding Window (Variable Size Window)

        # Substring Representation:
        #   - Maintain window [left, right]
        #   - Single hashmap: char -> remaining required count
        #   - targetCharsRemaining: tracks total chars still needed

        # Idea:
        #   - Expand right pointer to explore new character
        #   - Decreased count of remaining required count
        #   - When targetCharsRemaining == 0, window is valid
        #   - Shrink from left to minimize window
        #   - Track smallest valid window


        # sLen < tLen: substring not possible
        # tc: O(1)        
        if len(s) < len(t):
            return ""

        # Build required frequency map
        # sc: O(1)
        charCount = defaultdict(int)

        # tc: O(m)
        for ch in t:
            charCount[ch] += 1

        # Total chars still needed
        targetCharsRemaining = len(t)         

        # Sliding Window Variables
        # sc: O(1)

        # left boundary of substring
        left = 0

        # right boundary of substring
        right = 0

        
        # Track smallest window
        minWindow = (0, float("inf"))          

                       
        # tc: iterate over n O(n)
        while right < len(s):

            # Expand window
            # tc: O(1)
            char = s[right]

            if charCount[char] > 0:
                targetCharsRemaining -= 1

            charCount[char] -= 1

            # Shrink window while valid
            # tc: amortized O(n)
            while targetCharsRemaining == 0:

                # If smaller min window found, update
                if (right - left) < (minWindow]1] - minWindow]0]):
                    minWindow = (left, right)

                # Remove left character
                leftChar = s[left]
                charCount[leftChar] += 1

                # If removing breaks validity
                if charCount[leftChar] > 0:
                    targetCharsRemaining += 1

                # Shrink substring from left
                # tc: O(1)
                left += 1

            # Move right pointer
            right += 1

        # If no valid substring was found
        if minWindow]1] == float("inf"):
            return ""

        res = s[minWindow]0]:minWindow]1] + 1]

        # overall: tc O(n + m)
        # overall: sc O(1)
        return res

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

        # Sliding Window (Fixed Size Window)

        # Substring Representation:
        #   - Maintain window of size k
        #   - MaxHeap storing (-value, index)
        #   - Heap top always holds current window maximum

        # Idea:
        #   - Push first k elements into heap
        #   - For each new element:
        #       1. Push new element
        #       2. Remove stale elements (outside window) (index <= (right - k))
        #       3. Heap top is max of current window


        # Empty check:
        # tc: O(1)
        if not nums or k == 0:
            return []

        n = len(nums)

        # List of max values for each window
        # sc: O(n)
        result = []

        # maxHeap (minHeap with negative values)
        # (-value, index)
        # 
        maxHeap = []  

        # Sliding Window Variables
        # sc: O(1)

        # right boundary of substring
        right = 0

        # Initialize first window:
        # push first k elements to maxHeap
        # tc: O(k)
        while right < k:
            
            # tc: O(log k)
            heapq.heappush(maxHeap, (-nums[right], right))

            # Expand substring
            # tc: O(1)
            right += 1

        # MaxHeap:
        # root of maxHeap now holds the max of the current window,
        # so its holding the max for the first window,
        # we append to the result list
        peekMax = -maxHeap[0][0]
        result.append(peekMax)

    
        # tc: iterate over n O(n)
        while right < n:

            # Expand window
            newElem = nums[right]

            # Push new element: (-value, index)
            heapq.heappush(maxHeap, (-newElem, right))

            # Remove top of maxHeap if it is stale (outside window)
            while maxHeap[0][1] <= (right - k):
                heapq.heappop(maxHeap)

            # MaxHeap:
            # root of maxHeap now holds the max of the current window,
            # we append to the result list
            peekMax = -maxHeap[0][0]
            result.append(peekMax)

            # Expand substring
            # tc: O(1)
            right += 1

        # overall: tc O(n log k)
        # overall: sc O(k)
        return result

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

        # Sliding Window (Fixed Size Window)

        # Substring Representation
        #   - Maintain window of size k [left, right]
        #   - Monotonic Decreasing Deque storing indices
        #   - Front of deque always holds max element index

        # Idea:
        #   - Remove elements smaller than incoming element (from back)
        #   - Remove front if it exits window
        #   - Front of deque is always window max


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

        n = len(nums)

        # result list for each window
        res = []

        # stores elements in decreasing order
        dq = deque()

        # Sliding Window Variables
        # sc: O(1)

        # right boundary of substring
        right = 0

        # tc: iterate over n O(n)
        while right < n:

            # Remove elements smaller than incoming from back
            while dq and nums[dq[-1]] < nums[right]:
                dq.pop()

            dq.append(right)

            # Remove elements outside window from front
            while dq and dq[0] <= right - k:
                dq.popleft()

            dq.append(right)

            # Add to result when window is full
            if right >= k - 1:
                res.append(nums[dq[0]])
                
            # Expand substring
            # tc: O(1)
            right += 1

        # overall: tc
        # overall: sc
        return res

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

        # Sliding Window (Fixed Size Window)

        # Substring Representation:
        #   - Partition array into blocks of size k
        #   - leftMax[i]  = max from block start to i
        #   - rightMax[i] = max from block end to i (reverse scan)

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

        n = len(nums)

        leftMax = [0] * n
        rightMax = [0] * n

        # Build leftMax with two pointer style

        # Fill leftMax: scanning forward
        for i in range(n):

            if i % k == 0:

                # Start of block
                leftMax[i] = nums[i]
            else:
                leftMax[i] = max(leftMax[i-1], nums[i])

        # Build rightMax with two pointer style (reverse)

        # Fill rightMax: scanning backward
        for i in range(n-1, -1, -1):

            if (i+1) % k == 0 or i == n-1:

                # End of block
                rightMax[i] = nums[i]
            else:
                rightMax[i] = max(rightMax[i+1], nums[i])

        # Compute window maxes with explicit pointers

        # Compute sliding window max
        res = []
        left = 0
        right = k - 1

        while right < n:
            res.append(max(rightMax[left], leftMax[right]))
            left += 1
            right +=1

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

    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        
        # Sliding Window (Variable Size Window via Prefix Sum)

        # Substring Representation:
        #   - We process prefixSums while expanding right pointer
        #   - Instead of shrinking left manually,
        #     we use a hashmap to simulate all valid left boundaries
        #     by counting the number of times a prefixSum has occurred 

        # PrefixSum[0, right]
        #   - prefixSum represents the total sum from [0, right] 
        #     so prefixSum[1] => nums[0] + nums[1]
        #
        #   - When we expand our right boundary and it becomes fixed,
        #     we want to count how many inner subarrays END at this index whose sum == goal,
        #     here we can only change the left pointer
        
        # Finding Inner PrefixSum[i, right]
        #   - Suppose we have prefixSum from i to right, that can be represented by
        #       [i, right] = [0, right] - [0, i-1]      

        # Finding Starting Index i, so [i, right] == goal
        #   - For prefixSum[i, right] we want prefixSum == goal 
        #       [i, right]            == goal
        #       [0, right] - [0, i-1] == goal
        #       [0, right] - goal     == [0, i-1]
        #      
        #      So any subarray == [0, right] - goal
        #      will indicate there is a valid starting index at index i

        # Empty check
        if not nums:
            return 0

        n = len(nums)

        # HashMap: prefixSum -> number of occurrences
        # sc: O(n)
        prefixSumCounts = defaultdict(int)

        # Base Case: 
        # prefixSum from [0, i] where i == 0 is 0
        prefixSumCounts[0] = 1

        # Sliding Window Variables
        # tc: O(n)

        # right boundary of prefixSum [0, right]
        right = 0

        # PrefixSum for [0, right] as window expands
        prefixSum = 0

        # Count of prefixSum where prefixSum[i, right] == goal
        res = 0

        # tc: iterate over n O(n)
        while right < n:

            # Expand window
            # tc: O(1)
            newNum = nums[right]

            # Update prefixSum
            prefixSum += newNum

            # We have fixed the right boundary, 
            # the only thing that can change is the left boundary

            # Check how many valid indexes of i left boundaries exist
            prefix0Toi = prefixSum - goal

            # For each valid boundary
            if prefix0Toi in prefixSumCounts:

                # Number of subarrays that indicate a valid i boundary
                res += prefixSumCounts[prefix0Toi]

            # Record current prefixSum to occurrence count
            prefixSumCounts[prefixSum] += 1

            # Move right pointer
            right += 1

        # overall: tc O(n + m)
        # overall: sc O(1)        
        return res

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

        # Sliding Window (Variable Size Window)

        # Substring Representation:
        #   - Maintain window [left, right] representing the substring we can replace
        #   - Goal: Find minimum length substring which, when replaced, balances the string
        #   - Count of each character outside window should be <= n // 4
    
    
        n = len(s)
        target = n // 4

        # Count total occurrences of each character in s
        totalCount = Counter(s)
        
        # Only keep excess counts,
        # characters that already <= target are ignored
        excess = {c: max(0, totalCount[c] - target) for c in "QWER"}        
        
        # If there is no excess, string is already balanced
        if all(v == 0 for v in excess.values()):
            return 0

        # Sliding Window Variables
        # sc: O(1)
        left = 0
        right = 0

        # Initialize min length as length of full original string
        minLen = n 

        # tc: iterate over n O(n)
        while right < n: 

            # Expand window: 
            # decrease count for current character if it's in excess
            if s[right] in excess:
                excess[s[right]] -= 1

            # Shrink window while current window covers all excess characters
            while all(v <= 0 for v in excess.values()):
                # Update min length
                minLen = min(minLen, right - left + 1)

                # Shrink from left: restore character count if it was in excess
                if s[left] in excess:
                    excess[s[left]] += 1
                left += 1

            # Expand right pointer
            right += 1

        # overall: tc O(n)
        # overall: sc O(1)
        return minLen

    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        
        # Sliding Window + Two Pointers
        
        # Substring Representation:
        #   - Maintain window [left, right] representing the current substring of s
        #   - The window is valid if totalCost <= maxCost
        #   - Find the max length valid window

        # Idea:
        #   - For each character at index 'right', compute cost to change s[right] -> t[right]
        #   - Expand window by moving right pointer and accumulating totalCost
        #   - If totalCost exceeds maxCost, shrink window from left until valid
        #   - Track max window length during iteration

        n = len(s)
        
        # Sliding Window Variables
        # sc: O(1)
        left = 0
        right = 0


        totalCost = 0
        maxLen = 0

        # tc: iterate over n O(n)
        while right < n: 

            # Expand window: add cost of current character
            cost = abs(ord(s[right]) - ord(t[right]))
            totalCost += cost

            # Shrink window while total cost exceeds maxCost
            while totalCost > maxCost:
                totalCost -= abs(ord(s[left]) - ord(t[left]))
                left += 1
            
            windowLen = (right - left) + 1

            # Update maximum length of valid substring
            maxLen = max(maxLen, windowLen)

            # Move right pointer forward
            right += 1

        # overall: tc O(n)
        # overall: sc O(1)
        return maxLen

    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        
        # Sliding Window (Variable Size Window)

        # Substring Representation:
        #   - Maintain window [left, right] representing current subarray
        #   - Window is valid if it contains <= k distinct numbers
        #   - For exactly k distinct: count = atMostK(k) - atMostK(k-1)

        # Idea:
        #   - Use a sliding window to count number of subarrays
        #      with at most k distinct integers
        #   - For each right pointer expansion:
        #       1. Add nums[right] to window
        #       2. Shrink left while distinct count exceeds k
        #       3. Add window length (right - left + 1) to total count
        #   - Exact k distinct subarrays = atMostK(k) - atMostK(k-1)

        # Helper: count subarrays with at most k distinct integers
        # overall: tc O(n)
        # overall: sc O(n)
        def atMostK(nums, K):

            count = defaultdict(int)

            # Sliding Window Variables
            # sc: O(n) for hashmap
            left = 0
            res = 0
            distinct = 0


            # tc: iterate over n O(n)
            while right < n:

                # Expand window
                newNum = nums[right]

                # Check if new num has been found
                if freq[nums[right]] == 0:
                    distinct += 1

                # Increase num count 
                freq[nums[right]] += 1

                # Shrink window while distinct count exceeds k
                while k < distinct:

                    # Left window we are missing
                    losingNum = nums[left]
                    freq[losingNum] -= 1

                    # If we have lost all occurrences of a char
                    if freq[nums[left]] == 0:
                        distinct -= 1

                    # Shrink window
                    # tc: O(1)
                    left += 1

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

                # Expand right pointer
                right += 1

            return res

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

        # overall: tc O(n)
        # overall: sc O(n)
        return res

    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 findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
                
        # Binary Search + Sliding Window Approach

        # Idea:
        # 1. The closest k elements must form a contiguous subarray of length k.
        # 2. Use binary search to find the left boundary of that window.
        # 3. Compare distances from x for potential windows, and shrink towards the closest.
        
        n = len(arr)
        
        # Binary search boundaries for left index of window
        left = 0
        right = n - k  # window of size k, so left can go at most n-k
        
        # tc: binary search over n-k positions => O(log(n-k)) ~ O(log n)
        while left < right:
            mid = (left + right) // 2

            # Compare the distance of the edges of the window to x
            if x - arr[mid] > arr[mid + k] - x:
                # Move window right
                left = mid + 1
            else:
                # Move window left (or stay)
                right = mid
        
        # left now points to the start of the closest k elements
        result = arr[left:left + k]
        
        # overall: tc O(log(n-k) + k) ~ O(log n + k)
        # overall: sc O(k) for the result array
        return result

    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

        # overall: tc O()
        # overall: sc O()
        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