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:  

        # Space Optimization:
        #   - LeetCode measures peak memory usage at runtime, not just asymptotic SC
        #   - HashMap/HashSet solutions are O(n), but carry large constant factors:
        #       hash table buckets, key-value pairs, pointers, hashing overhead, etc
        #   - A list of integers in contiguous in memory with no overhead,
        #     making it significantly lighter in practice despite same O(n) SC
        #   - No early exist via set to preserve this space advantage

        # Sort By Value + Index Comparison

        # Representation:
        #   - Sort indices by their values in nums
        #   - Adjacent indices in sorted order are the closest value matches

        # Idea:
        #   - If any duplicate values exist, they will be adjacent after sorting
        #   - Sort indices based on original values
        #   - If duplicate is found, check if original indexes are within k
        #   - Avoids storing a window or hashmap entirely

        n = len(nums)

        # Empty Case:
        # if not enough days to have a duplicate
        if n <= 1 or k <= 0:
            return False

        # Create list of indices
        # tc: O(n)
        # sc: O(n)
        index = list(range(n))

        # Creates an array of indexes that maps to the new sorted array
        # ex:
        #      nums = [3,1,2], idx=[0,1,2]
        #      nums = [3,1,2], idx=[1,2,0]
        # tc: O(n log n)
        index.sort(key=lambda i: nums[i])

        # Check adjacent pairs in sorted order
        # tc: O(n)
        for i in range(1, n):

            currIndex = index[i]
            prevIndex = index[i-1]

            # Check: if adjacent values are duplicates
            if nums[currIndex] == nums[prevIndex]:

                # Boundaries of original indices
                left = min(currIndex, prevIndex)
                right = max(currIndex, prevIndex)

                # Distance between original indices
                distance = right - left

                # Check: if original indices are within k distance
                if distance <= k:
                    return True

        # No duplicates found within distance k

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

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        # Sliding Window + HashMap

        # Window Representation:
        #   - Width of [left, right]
        #   - Window size of max k
        #   - HashSet stores most recent index appearance for nums

        # Idea:
        #   - Slide window over num list and add index at right boundary
        #   - Check mri to determine if duplicate exists within window boundaries
    
        # Track more recent index appearance for num
        # sc: O(n)
        mostRecentIndex = {}

        # Sliding Window Variables
        # sc: O(1)

        # right boundary
        n = len(nums)
        right = 0

        # Empty Case:
        # if not enough days to have a duplicate
        if n <= 1 or k <= 0:
            return False

        # tc: iterate over n O(n)
        for right in range(n):

            currNum = nums[right]

            # Check: if num has already been seen
            # tc: O(1)
            if currNum in mostRecentIndex:

                #     k distance
                #  | ------------ |
                # left          right 

                # the furthest left index that is still within k distance
                left = right - k

                # previous occurrence of currNum
                prevIndex = mostRecentIndex[currNum]

                # Check: if previous num copy is within current window:
                if left <= prevIndex <= right:
                    return True

            # Implies: no duplicate exists
            # Then: update mri for num
            mostRecentIndex[currNum] = right

 
        # No duplicates found within distance k

        # tc: O(n)
        # overall: sc O(min(n, k))
        return False

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        # Sliding Window + HashSet

        # Window Representation:
        #   - Width of [left, right]
        #   - Window size of max k
        #   - HashSet stores elements currently inside window

        # Idea:
        #   - Slide window over num list and add num at right boundary
        #   - Check if num we added is already within window boundary
        #   - Keep max k elements within window boundaries
        #   - Remove elements from left boundary once window is large than size k

        n = len(nums)

        # Empty Case:
        # if not enough days to buy and sell in time
        if n <= 1 or k <= 0:
            return False

        # Sliding Window Data:
        # sc: up to O(k)
        window = set()

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

        # Early exit: if all elements are unique, no duplicates possible
        # tc: O(n)
        # sc: O(n)
        if len(window) == n:
            return False

        # tc: iterate over n O(n)
        for right in range(n):

            # Check: if num already exists within window range
            if nums[right] in window:
                return True

            # Add right index to sliding window and iterate:
            window.add(nums[right])

            # Remove left index from sliding window, if we've reached capacity, and iterate:
            if len(window) > k:
                window.remove(nums[left])
                left += 1

        # No duplicates found within distance k

        # overall: tc O(n)
        # overall: sc O(min(n, k))
        return False

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

        # 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)

        # Sliding Window Representation:

        # Data: max profit seen so far
        # sc: O(1)
        maxProfit = 0

        # Left Boundary: lowest buy price seen so far
        # tc: O(1)
        left = 0

        # Right Boundary: current price scanner
        # tc: O(1)
        right = 0

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

            # Grab current window boundaries
            # sc: O(1)
            buyPrice = prices[left]
            sellPrice = prices[right]

            # Check: can we make a profit (is current price higher than our current buy)
            # Then: calculate and compare profit
            if buyPrice < sellPrice:
                
                # Calculate profit
                profit = sellPrice - buyPrice

                # Compare profit
                maxProfit = max(maxProfit, profit)

            # Check: have we found a better buy price (is current price lower than our current buy)
            # Then: update our lowest buy (our left boundary)
            else:
                left = right

            # iterate current price scanner
            right += 1

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

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

        # 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:
        #   - Track lowest price
        #   - If current price is lower than buy price, we have found better buy price, reset window
        #   - If current price is higher than buy price, check if higher profit found

        # Sliding Window Representation:

        # Data: max profit seen so far
        maxProfit = 0

        # Left Boundary: lowest buy price seen so far
        minPrice = float('inf')

        # tc: iterate over n O(n)
        for price in prices:

            # if today has a lower buy price
            if price < minPrice:
                minPrice = price

            # if today has a better profit
            elif price - minPrice > maxProfit:
                maxProfit = price - minPrice

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

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

        # Dynamic Programming (Full DP Table)

        # Window Representation:
        #   - Maintain window within [i]
        #   - buyPrice[i][0]: best buy day so far:
        #       we represent this by min(-buyPrice) for easier later calculations
        #
        #   - buyPrice[i][1]: best profit price up to day i
        #       

        # Idea:
        #   - Always buy before you sell (<= index 1)
        #   - Check if new buy day found
        #   - Check if new best profit found


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

        n = len(prices)

        # Initialize DP:
        # sc: O(n)
        dp = []
        
        # Fill dp table:
        #   - dp[i][0]: best buy price up to day i
        #   - dp[i][1]: best profit price up to day i
        # tc: O(n)
        for i in range(n):
            dp.append([0, 0])

        
        # Initialize DP:
        # i = day
        # dp[i][0]: set best buy price to day 0
        # dp[i][1]: set best profit made up to day 0 
        #           (cannot buy and sell on same day, so profit on day 0 is 0)
        # tc: O(1)
        dp[0][0] = -prices[0]
        dp[0][1] = 0

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

            # Check: grab todays buy price
            # Use profit to explain our buy price:
            #     profit = hold + sellPrice
            #            = (-3) + 10
            #            = 7       
            todayPrice = -prices[i]

            # Check: grab best buy price up to yesterday
            bestBuyUpToYesterday = dp[i-1][0]

            # Check: grab new buy price
            dp[i][0] = max(bestBuyUpToYesterday, todayPrice)     

            # Check: todays profit
            todayProfit = bestBuyUpToYesterday + prices[i]
            
            # Check: grab new best profit, cannot sell today, so use yesterdays price    
            dp[i][1] = max(dp[i-1][1], todayProfit)


        # 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

        # Initialize Compressed DP:
        #   - min price up to day 0
        #   - max profit up to day 0
        bestBuyPrice = -prices[0]
        maxProfit = 0

        # start from second day
        # tc: iterate over n days O(n)
        for i in range(1, n):
            
            # Put buy price as negative,
            # to ensure we always subtract it from out buy price
            #     profit = hold + sellPrice
            #            = (-3) + 10
            #            = 7       
            todayPrice = -prices[i]

            # Check: compare best buy price up to yesterday to today buy price
            bestBuyPrice = max(bestBuyPrice, todayPrice)

            todayProfit = bestBuyPrice + prices[i]

            # profit = hold + sellPrice
            #        = (-3) + 10
            #        = 7
            maxProfit = max(maxProfit, todayProfit)  

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

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

        # Sliding Window (Variable Size)

        # Window Representation:
        #   - Maintain window [left, right]
        #   - HashSet stores most recent index appearance for nums
        #   - Window will contain no duplicates

        # Idea:
        #   - Expand right pointer to explore new characters
        #   - If new character results in a duplicate,
        #     move the left window boundary to 1 in front of the duplicate

        n = len(s)-1

        # Track more recent index appearance for char
        mostRecentIndex = {} 

        # 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 mostRecentIndex:
                    
                    prevIndex = mostRecentIndex[newChar]
                    
                    if left <= prevIndex <= right:

                        # Move left pointer to remove previous duplicate from window
                        left = prevIndex + 1

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

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

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

                # Iterate right pointer to continue window shifting
                # tc: O(1)
                right += 1
            
        # overall: tc O(n)
        # overall: sc O(min(n, k))
        return maxLen

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

    # Sliding Window (Variable Size Window)

    # Window Representation:
    #   - Maintain window [left, right]
    #   - HashSet stores unique characters currently inside window

    # Idea:
    #   - Expand right to add new characters
    #   - If duplicate found, shrink from left until duplicate is removed
    #   - Track longest window seen with no duplicates

    n = len(s)

    # Sliding Window Data:
    # sc: O(k)
    window = set()

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

    # Track longest valid window
    maxLen = 0

    # tc: iterate over n O(n)
    for right in range(n):

        # Shrink from left until duplicate is removed
        # tc: O(1) amortized
        while s[right] in window:
            window.remove(s[left])
            left += 1

        # Add incoming character to window
        # tc: O(1)
        window.add(s[right])

        # Update max length if current window is larger
        # tc: O(1)
        maxLen = max(maxLen, len(window))

    # overall: tc O(n)
    # overall: sc O(min(n, k))
    return maxLen

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

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

        # Idea:
        #   - Expand right pointer to explore new character
        #   - maxFreq will hold the mostOccur char in window
        #   - Window length of size right - left + 1
        
        # Trick:
        #   - We need allOtherChars in window to be <= k, so that we know
        #     we can replace allOtherChars with the mostOccur
        #   - If allOtherChars is greater than k (allOtherChars > k),
        #     we simply shrink from left until we can replace allOtherChars,
        #     when allOtherChars is less than or equal to k, (allOtherChars <= k)

        n = len(s)

        # char count within window boundaries
        count = defaultdict(int)

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

        # Sliding Window Data
        # sc: O(1)
        # mostOccur: most occurring character in window
        mostOccur = 0  
        # max length seen so far
        maxLen = 0

        # tc: iterate over n O(n)
        for right in range(n):

            # Character we just encountered
            # tc: O(1)
            currChar = s[right]
            charCount[currChar] += 1

            # Update mostOccur in window
            # tc: O(1)
            mostOccur = max(mostOccur, charCount[currChar])

            # length of curr window
            currWindowLen = right - left + 1

            # how many other chars exists, (anything that is not mostOccur)
            allOtherChars = currWindowLen - mostOccur

            # We need allOtherChars to be less than k (num of chars we can replace),
            # so that we can replace allOtherChars with the mostOccur.
            # thus, shrink window from left by 1 until allOtherChars is valid
            # tc: O(1) amortized
            while k < allOtherChars:

                # Note: we do NOT update mostOccur here
                # While shrinking, the mostOccur may become stale
                #   - true max mostOccur may have decreased
                #   - mostOccur char may have shifted to a different character

                # This is fine because:
                #   - for the current window from [left:right], we have already agreed that
                #     mostOccur is the highest char
                #   - so even if we shrink and remove
                
                # A stale mostOccur will make allOtherChars smaller than actual 
                #   - underestimating allOtherChars
                
                # This is safe because: 
                #   - No char can exceed the current mostOccur while shrinking,
                #     since we are only shrinking from the left and not modifying right
                #   - Regardless, we need to shrink because an invalid window 
                #     won't count towards our maxLen
                
                # Thus mostOccur:
                #   - not acting as a true most occurring character
                #   - acting as a flag for the original mostOccur for original window
                #     that existed before shrinking
                
                # Remove left character from window
                charCount[s[left]] -= 1
                left += 1

                # Recompute currWindowLen and allOtherChars after shrink
                currWindowLen = right - left + 1
                allOtherChars = currWindowLen - mostOccur


            
            # Once allOtherChars is valid, check maxLen
            maxLen = max(maxLen, currWindowLen)

        # 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)

        n1 = len(s1)
        n2 = len(s2)

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

        # s1 Frequency
        # tc: O(n)
        # sc: O(n)
        needleCharCount = defaultdict(int)
        for c in s1:
            needleCharCount[c] += 1

        # Substring window frequency
        # sc: O(1)
        windowCharCount = defaultdict(int)
        
        # left boundary of current substring
        left = 0

        # right boundary of current substring
        right = 0

        # tc: iterate over n O(n)
        for right in range(n2):

            # Add new character to substring
            # tc: O(1)
            rightChar = s2[right]
            windowCharCount[rightChar] += 1

            currWindowLen = right - left + 1

            # Optimization:
            # While window size is longer than  needle size, shrink
            # tc: O(1)
            while n1 < currWindowLen:

                # Remove character from substring
                leftChar = s2[left]

                # Update substring character count
                windowCharCount[leftChar] -= 1

                # Remove zero frequency keys
                if windowCharCount[leftChar] == 0:
                    # need to remove empty char counts, 
                    # so we can match window hashmap to needle hashmap 
                    del windowCharCount[leftChar]
                
                # Shrink substring from left
                # tc: O(1)
                left += 1

                currWindowLen = right - left + 1
            
            # Window is valid size,
            # check if permutation found
            if windowCharCount == needleCharCount:
                return True

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

    def checkInclusion(self, s1: str, s2: str) -> bool:
        
        # Sliding Window (Fixed Size Window)

        # Window Representation:
        #   - Fixed window of size len(s1)
        #   - Two frequency arrays of size 26 (one per lowercase letter)
        #   - needleCharCount: frequency of each char in s1
        #   - fixedWindowCharCount: frequency of each char in current window of s2

        # Idea:
        #   - Build needleCharCount fixedWindowCharCount from s1
        #   - Seed first window of s2 into fixedWindowCharCount
        #   - Slide window across s2: remove leftmost char, add new rightmost char
        #   - If fixedWindowCharCount == needleCharCount at any point, window is a permutation of s1

        # Lowercase Ascii Index Shifting:
        # lowercase chars start 97, so if we want 'a' to go from 97 to 0,
        # we just subtract 97 from any and all chars.
        # Now instead of 97 -> 122, we get 0 -> 26

        # s2 too short to contain s1
        # tc: O(1)
        if len(s2) < len(s1):
            return False

        # Fixed Window Iteration:
        # Create a fixed window size based on the needle size.
        # Calculate the window on the leftmost indexes of the haystack.
        # Iterate the fixed window over the haystack while simply
        # adding the right char and removing the left char.
        # Compare each iteration to expected needleCharCount

        # Frequency arrays for each lowercase letter a-z
        # sc: O(1) fixed size 26
        needleCharCount = [0] * 26
        fixedWindowCharCount = [0] * 26

        # Fixed window right boundary
        fixedWindowRight = len(s1)

        # Seed needleCharCount and first window of s2
        # tc: O(k) where k = len(s1)
        for i in range(fixedWindowRight):
            # populate the expected needle char count
            needleCharCount[ord(s1[i]) - 97] += 1
            # populate the first [0, right] chars in the haystack
            fixedWindowCharCount[ord(s2[i]) - 97] += 1

        # Check if first fixed window char count matches needle char count
        # tc: O(1)
        if fixedWindowCharCount == needleCharCount:
            return True

        # Slide window across remaining chars in s2
        # tc: O(n)
        for right in range(fixedWindowRight, len(s2)):

            # Grab left boundary index for fixed window
            left = right - fixedWindowRight

            # Iterate fixed window, remove left char, add right char
            fixedWindowCharCount[ord(s2[left]) - 97] -= 1
            fixedWindowCharCount[ord(s2[right]) - 97] += 1

            # Check if window char count matches needle char count
            # tc: O(1)
            if fixedWindowCharCount == needleCharCount:
                return True

        # No permutation found
        
        # overall: tc O(n + k)
        # overall: sc O(1)
        return False

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

        # Sliding Window (Fixed Size Window)

        # Substring Representation:
        #   - Maintain window [left, right]
        #   - Two Hashmaps:
        #       needleFreq -> required counts
        #       windowFreq -> current window counts

        # Idea:
        #   - Expand right pointer to explore new character
        #   - Track how many required character are satisfied via needleFreq
        #   - While required characters are 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 needle character map
        # sc: O(m)
        needleCharCount = defaultdict(int)
        for c in t:
            needleCharCount[c] += 1

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

        # Sliding Window Data (3)
        # Frequency map for curr chars in window (1)
        # sc: O(1)
        windowCharCount = defaultdict(int)

        # length and starting index of smallest window so far (2)
        minLen = float('inf')
        minStart = 0

        # Flags for unique chars slots from needle hashmap length (3)
        needCharSlots = len(needleCharCount) 
        haveCharSlots = 0                 

        # tc: iterate over n O(n)
        for right in range(len(s)):

            # Expand window
            # tc: O(1)
            rightChar = s[right]
            windowCharCount[rightChar] += 1

            # If char is a slot char with requirements
            if rightChar in needleCharCount:

                # If char has met requirements
                if windowCharCount[rightChar] == needleCharCount[rightChar]:
                    haveCharSlots += 1


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

                # Remove left character
                leftChar = s[left]
                windowCharCount[leftChar] -= 1
                
                # If char is a slot char with requirements
                if leftChar in needleCharCount:

                    # If char no longer meets requirements
                    if  windowCharCount[leftChar] < needleCharCount[leftChar]:
                        haveCharSlots -= 1

                # Shrink substring from left
                # tc: O(1)
                left += 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(n)
        return res

    def minWindow(self, s: str, t: str) -> str:

        # 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
        #   - Decrease 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)
        needleCharCount = defaultdict(int)

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

        # Total chars still needed
        globalRemainingCountAcrossChars = len(t)         

        # Sliding Window Variables
        # sc: O(1)
        left = 0
        right = 0
        minWindow = (0, float("inf"))          

        # tc: iterate over n O(n)
        for right in range(len(s)):

            # Expand window
            # tc: O(1)
            rightChar = s[right]
            
            # Note:
            # to start, needleCharCount hashmap will only contain values of chars that 
            # we need for the needle.
            # This means all other possible keys, are set to 0, and moving forward,
            # can only be less than or equal to 0 (regardless of adding or removing).
            # Thus, to track chars that are in the needle,
            # we only count chars that at some point have a positive count,
            # to contribute towards decreasing or increasing the global remaining 
            stillNeedThisMany = needleCharCount[rightChar]

            if stillNeedThisMany > 0:
                globalRemainingCountAcrossChars -= 1

            needleCharCount[rightChar] -= 1

            # Shrink window while its valid, so we can find the min valid window
            # tc: amortized O(n)
            while globalRemainingCountAcrossChars == 0:

                currWindowLen = right - left + 1
                currMinWindowLen = minWindow[1] - minWindow[0] + 1

                # If smaller min window found, update min
                if currWindowLen < currMinWindowLen:
                    minWindow = (left, right)

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

                # If after excluding this char we now need copies of this char,
                # we can count it towards hurting and increasing the global counter
                stillNeedThisMany = needleCharCount[leftChar]

                if stillNeedThisMany > 0:
                    globalRemainingCountAcrossChars += 1

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

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

        # Grab min window
        res = s[minWindow[0]:minWindow[1] + 1]

        # overall: tc O(n + m)
        # overall: sc O(n)
        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():
        #   - a Python minHeap with negative values, resulting in a maxHeap
        #   - O(log n) insertion and removal 

        # MaxHeap data representation: (-value, index)
        #   - Need the -value to turn MinHeap into MaxHeap 
        #   - Need the index to check if top of heap is outside window
        maxHeap = []  

        # MaxHeap top representation (maxHeap[0]):
        #   - Top: largest element index in current window
        #   - All other: no guarantee for any other element, 
        #              we are only guaranteed that the top is the current max in the MaxHeap
        # 

        # Sliding Window Variables
        # sc: O(1)
        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(n)
        return result

    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 []

        # We will split the original nums array into k sized blocks:
        # index:   0  1  2    3  4  5    6  7
        # nums:    1  3 -1   -3  5  3    6  7
        # blocks: [------]  [------]   [----]
        #           B0         B1        B2

        # Blocks are based only on index position and k size
        # They are not based on the direction of the scan 

        n = len(nums)

        # L to R Max Values, to L Max Values
        leftMax = [0] * n
        rightMax = [0] * n

        # Fill leftMax: find the running max on a per block basis L to R
        for i in range(n):

            # Start of new block: max is first element of block
            if i % k == 0:
                leftMax[i] = nums[i]

            # In Middle of block: compare currNum to prevMax
            else:
                leftMax[i] = max(leftMax[i-1], nums[i])

        # Fill rightMax: find the running max on a per block basis R to L
        for i in range(n-1, -1, -1):

            # Start of new block: max is first element of block
            if (i+1) % k == 0 or i == n-1:
                rightMax[i] = nums[i]

            # In Middle of block: compare currNum to prevMax
            else:
                rightMax[i] = max(rightMax[i+1], nums[i])

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

    
        # -----------------------------
        # Combining Precomputed with Fixed Window:
        # we are iterating a fixed window of size k:

        # Case 1: fixed window fully inside block
        #
        #   [  Window   ]
        #   [   BLOCK   ]
        #  

        # Case 2: fixed window spans 2 blocks
        #
        #     [  Window   ]
        # [ BLOCK A ][ BLOCK B ]


        # -----------------------------
        # Grabbing Farthest Data Available To Use From Left and Right:

        # Case 1: fixed window fully inside block
        #
        #   [  Window   ]
        #   [   BLOCK   ]
        #   ^           ^
        #   R           L

        # Case 2: fixed window spans 2 blocks
        #
        #     [  Window   ]
        # [ BLOCK A ][ BLOCK B ]
        #     ^           ^
        #     R           L

        # -----------------------------
        # Window Max Coverage:
        #       R = index max from iterating Right to Left (<---)
        #       L = index max from iterating Left to Right (--->)

        # Case 1: Entire Window Is Accounted For
        #
        #   [  Window   ]
        #   [   BLOCK   ]
        #   ^           ^
        #   R --------- L        
        #  (<---)     (--->)

        # Case 2: Entire Window Is Accounted For
        #
        #     [  Window   ]
        # [ BLOCK A ][ BLOCK B ]
        #     ^           ^
        #     R --------- L        
        #    (<---)     (--->)
        
        # tc: iterate over nums array O(n)
        while right < n:

            # Re: see above diagrams
            res.append(max(rightMax[left], leftMax[right]))
            left += 1
            right +=1

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

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

        # Sliding Window (Fixed Size Window) + Monotonic Deque
        
        # Window Representation:
        #   - Maintain a monotonic decreasing deque
        #   - Deque stores actual values (not indices)
        #   - Front of deque is always the max of current window

        # Idea:
        #   - Before adding new element, pop from back any values
        #     smaller than it (they can never be the max)
        #   - When window slides, pop from front if it equals
        #     the element being removed (nums[i])
        #   - Front of deque is always current window max

        # Unsafe For Duplicates:
        #   - Stores values instead of indices
        #   - When removing outgoing element, we compare by value not position
        #   - If duplicate values exist, we may accidentally remove the wrong copy

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

        n = len(nums)

        # result list for each window
        # sc: O(n)
        res = []

        # Deque():
        #   - a double ended queue
        #   - O(1) insertion and removal from both sides

        # Deque left and right ends representation:
        #   - Front (left end): largest element value in current window
        #     dq[0] always holds the current window max value
        #   - Back (right end): most recently added value
        #     dq[-1] holds the smallest element seen so far

        # Monotonic decreasing order means:
        #   High -> Low

        # left (high)             right (low)
        # [ val=8,  val=6,  val=3,  val=1 ]  Our Queue: Monotonic values always decreasing

        # stores values in monotonic decreasing order
        # sc: O(k)
        dq = deque()

        # Initialize first window:
        # Grab first k elements and place into deque
        # tc: O(k)
        for i in nums[:k]:

            # Monotonic Property:
            # Remove elements smaller than new num from right side to keep Monotonic High -> Low
            # tc: O(1) amortized
            while dq and i > dq[-1]:
                dq.pop()

            # Append new value after ensuring Monotonic High -> Low
            dq.append(i)

        # Deque front now holds max value of first window
        res = [dq[0]]

        # Slide window across remaining elements
        # tc: O(n - k)
        for i, x in enumerate(nums[k:]):

            # Sliding Window Single Iteration:
            # since at most, we are only adding 1 new element,
            # since we have a fixed window size,
            # at most, only 1 old element can go stale (out of bounds of the window)

            # Unsafe Duplicate Stale Check:
            # Since we store values instead of indices,
            # we identify the outgoing element by value comparison
            # nums[i] is the element leaving the window
            # Risk: if duplicates exist, may remove the wrong copy
            # tc: O(1)
            outgoingVal = nums[i]
            if dq[0] == outgoingVal:
                dq.popleft()

            # Monotonic Property:
            # Remove elements smaller than new num from right side to keep Monotonic High -> Low
            # tc: O(1) amortized
            while dq and x > dq[-1]:
                dq.pop()

            # Append new value after ensuring Monotonic High -> Low
            dq.append(x)

            # Deque front now holds max value of current window
            res.append(dq[0])

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

    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

        # Safe For Duplicates:
        #   - Stores indices instead of values
        #   - When removing outgoing element, we compare by index not value
        #   - Each index is unique, so we always know exactly which element is leaving
        #   - Duplicate values are handled correctly since we never confuse two
        #     elements at different positions

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

        n = len(nums)

        # result list for each window
        # sc: O(n)
        res = []

        # Deque():
        #   - a double ended queue
        #   - O(1) insertion and removal from both sides

        # Deque left and right ends representation:
        #   - Front (left end): largest element index in current window
        #     dq[0] always holds the index of the current window max
        #   - Back (right end): most recently added index
        #     dp[-1] holds the index of the smallest element seen so far 

        # Monotonic decreasing order means:
        #   High -> Low

        # left (high)             right (low)
        # [ idx=2,  idx=4,  idx=5,  idx=7 ]  Our Queue: Monotonic Increasing Indexes
        # [ val=8,  val=6,  val=3,  val=1 ]  We Can Access: Values always Monotonic Decreasing


        # stores indices in monotonic decreasing order of their values
        # sc: O(k)
        dq = deque()

        # Initialize first window:
        # Grab first k elements and place into deque
        # tc: O(k)
        for right in range(k):

            # Monotonic Property:
            # Remove elements smaller than new num from right side to keep Monotonic High -> Low
            # tc: O(1) amortized
            while dq and nums[dq[-1]] < nums[right]:
                dq.pop()

        # Append new index after ensuring Monotonic High -> Low
        dq.append(right)


        # tc: iterate over n O(n)
        for right in range(n):

            
            # Monotonic Property:
            # Remove elements smaller new num from the right side to keep Monotonic High -> Low
            # tc: O(1) amortized
            while dq and nums[dq[-1]] < nums[right]:
                dq.pop()

            # Append new num after ensuring Monotonic High -> Low
            dq.append(right)

            # Sliding Window Single Iteration:
            # since at most, we are only adding 1 new element, 
            # since we have a fixed window size,
            # at most, only 1 old element can go stale (out of bounds of the window)
            
            # Monotonic Trick:
            # Since we keeping both:
            #   - Monotonic High -> Low
            #   - Iterating by 1 Index at a time

            # left (high)             right (low)
            # [ idx=2,  idx=4,  idx=5,  idx=7 ]  Our Queue: Monotonic Increasing Indexes
            # [ val=8,  val=6,  val=3,  val=1 ]  We Can Access: Values always Monotonic Decreasing

            # So we only have to check if the highest value,
            # which by definition will have the lowest index (oldest value in the deque)
            # is now out of bounds of the fixed window

            left = right - k
            HighestValueIndex = dq[0]

            # Remove stale highest number from front
            # tc: O(1)
            if not left <= HighestValueIndex <= right:
                dq.popleft()

            # Deque front now holds max index of current window
            res.append(nums[dq[0]])


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

    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
               
        # Two Pointer (Variable Size Window)

        # Substring Representation:
        #   - Maintain window [left, right]
        #   - curr_sum tracks sum of current window

        # Idea:
        #   - Directly counting subarrays with sum == goal is hard
        #     with two pointers because we can't know when to stop shrinking
        #   - Instead, count subarrays with sum <= goal via atMost()
        #   - exactly(goal) = atMost(goal) - atMost(goal - 1)
        #   - Inside atMost: expand right, shrink left when sum > goal,
        #     right - left + 1 counts all valid subarrays ending at right

        # goal = 2
        # nums = [1, 0, 1, 0, 1]
        
        # --------------------------------------
        # atMost(2): all windows with sum <= 2
        # nums = [1, 0, 1, 0, 1]
        #         LR                currSum=1, res += 1 (1 subarray  ending at R)
        #         L  R              currSum=1, res += 2 (2 subarrays ending at R)
        #         L     R           currSum=2, res += 3 (3 subarrays ending at R)
        #         L        R        currSum=2, res += 4 (4 subarrays ending at R)
        #            L        R     currSum=3 -> shrink -> currSum=2, res += 4 (4 subarrays ending at R)
        # atMost(2) total = 1+2+3+4+4 = 14
        #
        # --------------------------------------
        # atMost(1): all windows with sum <= 1
        # nums = [1, 0, 1, 0, 1]
        #         LR                currSum=1, res += 1 (1 subarray  ending at R)
        #         L  R              currSum=1, res += 2 (2 subarrays ending at R)
        #            L  R           currSum=2 -> shrink -> currSum=1, res += 2 (2 subarrays ending at R)
        #            L     R        currSum=1, res += 3 (3 subarrays ending at R)
        #               L     R     currSum=2 -> shrink -> currSum=1, res += 2 (2 subarrays ending at R)
        # atMost(1) total = 1+2+2+3+2 = 10
        # --------------------------------------
        # exactly(2) = atMost(2) - atMost(1) = 14 - 10 = 4
        #   [1, 0, 1]
        #   [1, 0, 1, 0]
        #   [0, 1, 0, 1]
        #   [1, 0, 1]

        # Only valid because nums contains only 0 and 1:
        # shrinking window always decreases sum predictably
        # tc: O(1)
        def atMost(goal) -> int:

            # Guard against negative goal
            if goal < 0:
                return 0

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

            currSum = 0
            res = 0

            # tc: iterate over n O(n)
            for right in range(len(nums)):

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

                # Shrink window until sum <= goal
                # tc: O(1) amortized
                while currSum > goal:
                    currSum -= nums[left]
                    left += 1

                # All subarrays ending at right with sum <= goal
                # tc: O(1)
                windowLen = right - left + 1

                # Add to total res
                res += windowLen

            return res

        # exactly(goal) = atMost(goal) - atMost(goal - 1)
        # overall: tc O(n)
        # overall: sc O(1)
        return atMost(goal) - atMost(goal - 1)

    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        
        # Prefix Sum + HashMap

        # Representation:
        #   - prefix_count[s] = number of times prefix sum s has occurred
        #   - curr_sum = running prefix sum up to current index

        # Idea:
        #   - For each index, check how many previous prefix sums
        #     equal curr_sum - goal
        #   - If prefix_count[curr_sum - goal] exists, those subarrays
        #     all sum to goal
        #   - prefix_count[0] = 1 accounts for subarrays starting at index 0

        # goal = 2
        # nums = [1, 0, 1, 0, 1]
        
        # nums = [1, 0, 1, 0, 1]
        # vaild: [.......]
        #        L       R
        #        currSum = 2


        #        exludingSum = 1
        #        [....]       
        # nums = [1, 0, 1, 0, 1]
        # valid:        [......]
        #               L      R
        #               currSum = 3

        # goal - currSum = exludingSum
        # 3 - 2 = 1


        n = len(nums)
        
        # Empty check
        # tc: O(1)
        if n == 0:
            return 0

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

        # Base case: empty prefix has sum 0, seen once
        # tc: O(1)
        prefixSumCounts[0] = 1

        # Running prefix sum
        currSum = 0

        # Total valid subarrays found
        res = 0

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

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

            # Expand prefix sum
            # tc: O(1)
            currSum += nums[right]

            # If: prefixSum is higher than goal,
            # check if we can restrict left, so that we exclude enough numbers
            # to get our prefixSum back down to goal
            # tc: O(1)
            if currSum >= goal:

                # Check Target:
                # if at any point when iterating left to right,
                # the prefixSum added up to this target
                excludingSum = currSum - goal

                # Check Times:
                # number of times we encountered the target,
                # this tells us how many places we can shift left
                # to exclude numbers to get our prefixSum back down to goal
                excludingSumTimes = prefixSumCounts[excludingSum]

                # Add Times:
                # each location we can move left to,
                # is another prefixSum window that can be restricted via left to achieve goal
                res += excludingSumTimes

            # Record current prefixSum to occurrence count
            # tc: O(1)
            prefixSumCounts[currSum] += 1

            # Move right pointer
            right += 1

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

    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        
        # Prefix Sum + Array of (N+1)

        # Representation:
        #   - prefix_count[s] = number of times prefix sum s has occurred
        #   - curr_sum = running prefix sum up to current index

        # Idea:
        #   - For each index, check how many previous prefix sums
        #     equal curr_sum - goal
        #   - If prefix_count[curr_sum - goal] exists, those subarrays
        #     all sum to goal
        #   - prefix_count[0] = 1 accounts for subarrays starting at index 0

        # goal = 2
        # nums = [1, 0, 1, 0, 1]
        
        # nums = [1, 0, 1, 0, 1]
        # vaild: [.......]
        #        L       R
        #        currSum = 2


        #        exludingSum = 1
        #        [....]       
        # nums = [1, 0, 1, 0, 1]
        # valid:        [......]
        #               L      R
        #               currSum = 3

        # goal - currSum = exludingSum
        # 3 - 2 = 1

        n = len(nums)
        
        # Empty check
        # tc: O(1)
        if n == 0:
            return 0

        # Tracks for up to all possible sums (everything set to 1)
        # how many times we've seen a certain sum
        # sc: O(n)
        prefixSumCount = [0] * (n + 1)

        # Base case: we encounter the sum 0, for the first time
        # tc: O(1)
        prefixSumCount[0] = 1

        # Sum from left up to right
        currSum = 0

        # Total valid subarrays found
        res = 0

        # tc: iterate over n O(n)
        for num in nums:

            # Expand prefix sum
            # tc: O(1)
            currSum += num

            # If: currSum is higher than goal,
            # check if we can restrict left, so that we exclude enough numbers
            # to get our currSum back down to goal
            # tc: O(1)
            if currSum >= goal:
                
                # Check Target: 
                # if at any point when iterating left to right,
                # the currSum added up to this target
                exludingSum = currSum - goal 

                # Check Times:
                # check number of times we encountered the target,
                # this tells us how many places we can shift left to exlucde numbers to get our currSum back down to goal
                exludingSumTimes = prefixSumCount[exludingSum]

                # Add Times: 
                # each location we can move left to, 
                # is another currSum window that can be restricted via left to achieve goal
                res += exludingSumTimes

            # Record current prefix sum to use in future
            # tc: O(1)
            prefixSumCount[currSum] += 1

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

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

        # Sliding Window (Variable Size Window)

        # String Representation:
        #   - Maintain variable window [left, right]
        #   - Current window represents the substring we will replace
        #   - Frequencies OUTSIDE the window must all be <= target

        # Idea:
        #   - Store frequencies of chars OUTSIDE current window
        #   - Expand right to bring chars INTO window (removing from outside freq)
        #   - Once all outside frequencies <= target, window is valid
        #   - Shrink left to minimize valid window
        #   - Track smallest valid window seen

        # Balanced String:
        #   - 4 possible characters: Q W E R
        #   - Each must appear exactly len(s) // 4 times
        #   - Any character appearing more than target times needs replacement
        #
        #   e.g. s = "QWER", target = 1
        #        outsideCount = {Q:1, W:1, E:1, R:1} -> already balanced
        #
        #   e.g. s = "QQWE", target = 1
        #        outsideCount = {Q:2, W:1, E:1, R:0}
        #        Q exceeds target by 1, need to replace 1 char in window

        n = len(s)

        # Target frequency for each character:
        #   - The string s has n characters, and 4 possible characters (Q W E R)
        #   - A perfectly balanced string would have each character appear n // 4 times
        # tc: O(1)
        # sc: O(1)
        target = n // 4

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

        # Frequency HashMap:
        #   - Stores frequencies of chars OUTSIDE current window
        #   - Only 4 possible characters Q W E R
        # sc: O(1)
        outsideCount = defaultdict(int)
        for c in s:
            outsideCount[c] += 1

        # Minimum valid window size
        minLen = float('inf')

        # Early Exit:
        #   - If no character exceeds target balance count
        #   - Then all characters == target, 
        #     since you can't have any char count above target
        #     without another char count below target to compensate leading to unbalance
        # tc: O(1)
        if max(outsideCount.values()) <= target:
            return 0

        # Expand sliding window
        # tc: O(n)
        for right in range(n):

            # New character has entered window,
            # remove count from outside window tracker
            rightChar = s[right]
            outsideCount[rightChar] -= 1

            # Shrink from left while valid outside conditions:
            #   - All outside frequencies <= target => string is balanced
            #   - Window pointers are still valid
            # tc: O(1) amortized
            while max(outsideCount.values()) <= target and left <= right:

                # Check curr valid window
                currWindowLen = right - left + 1
                minLen = min(minLen, currWindowLen)

                # Remove char from window,
                # add it back to outside count frequencies
                # tc: O(1)
                leftChar = s[left]
                outsideCount[leftChar] += 1

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

        # MinLen:
        # smallest window available, with a valid outside count

        # The window needs to be just large enough to absorb all excess, minLen,
        # which tells you the minimum number of characters you need to replace.
        # You don't need to know exactly what to replace them with, just that 
        # a replacement of that size exists that can fix the balance

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