Sliding Window¶

Table of Content

TODO’s¶

Todo

Why Not?

Todo

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (Medium)

from collections import deque

def longestSubarray(nums: List[int], limit: int) -> int:
   n = len(nums)
   maxDeque, minDeque = deque(), deque()  # Deques to store indices of max and min elements
   left = right = 0
   maxi = 0

   while right < n:
      # Expansion
      while maxDeque and nums[right] > nums[maxDeque[-1]]:
            maxDeque.pop()
      while minDeque and nums[right] < nums[minDeque[-1]]:
            minDeque.pop()
      maxDeque.append(right)
      minDeque.append(right)

      # Check if current window exceeds limit
      while nums[maxDeque[0]] - nums[minDeque[0]] > limit:
            # Shrinking
            if left == maxDeque[0]:
               maxDeque.popleft()
            if left == minDeque[0]:
               minDeque.popleft()
            left += 1
      right += 1

      # Logic
      maxi = max(maxi, right - left)

   return maxi

395. Longest Substring with At Least K Repeating Characters (Medium)

def longestSubstring(self, s: str, k: int) -> int:
   def atMostKUniqueChars(maxUnique):
         n = len(s)
         left = right = 0
         counter = collections.Counter()
         uniqueChars = 0  # Number of unique characters in the current window
         countAtLeastK = 0  # Number of characters that appear at least k times in the current window
         longest = 0

         while right < n:
            # Expansion
            if counter[s[right]] == 0:
               uniqueChars += 1
            counter[s[right]] += 1
            if counter[s[right]] == k:
               countAtLeastK += 1
            right += 1

            # Shrinking
            while left < right and uniqueChars > maxUnique:
               if counter[s[left]] == k:
                     countAtLeastK -= 1
               counter[s[left]] -= 1
               if counter[s[left]] == 0:
                     uniqueChars -= 1
               left += 1

            # Logic
            if uniqueChars == countAtLeastK:
               longest = max(longest, right - left)

         return longest

   maxUniqueChars = len(set(s))  # Maximum possible unique characters in s
   maxi = 0
   for maxUnique in range(1, maxUniqueChars + 1):
         maxi = max(maxi, atMostKUniqueChars(maxUnique))

   return maxi

1156. Swap For Longest Repeated Character Substring (Medium)

def maxRepOpt1(self, text: str) -> int:
   counter = collections.Counter(text)
   left = right = 0
   n = len(text)
   maxi = 0
   freqCounter = collections.defaultdict(int)

   # Iterate through the string with a sliding window
   while right < n:
         # Expand the window
         freqCounter[text[right]] += 1
         right += 1

         # Check if window is valid - contains more than one type of character more than once
         while (right - left) - max(freqCounter.values()) > 1:
            # Shrink the window from the left
            freqCounter[text[left]] -= 1
            left += 1

         # Update maxi to the max length of the window considering all instances of the character in text
         # It considers swapping one character if it increases the window size and if another instance of the character exists outside the current window
         maxi = max(maxi, min((right - left), counter[text[right-1]]))

   return maxi

Tips¶

All sliding problem will have similar code pattern, with:

Expansion
Shrinking
Problem Logic

But, the problem logic determines which data structure to use:

Unique elements = set or dict
Frequencies = dict
Sum/Average = prefix sum or maintaining total
Max/Min element = deque

Sliding Window¶

TODO’s¶

Tips¶

Visualize me!¶