13. Sliding Window

A. General Introduction

I. What is it?

A powerful algorithmic mental model.

  • Usually involves iterable/sequential data structures.
    • contiguous sequence of elements
    • strings, arrays, linked lists, etc.
  • Goal: Min, Max, Longest, Shortest, Contained
    • Calculating somthing: Average, sum, etc.

II. Lets meet the variants

Some variants of the 'problem'
Some variants of the ‘problem’
  1. Fixed length variant

    • max sum of subarray of size k
  2. Dynamic variant

    • smallest sum that is greater than or equal to a target
  3. Dynamic variant w/ Auxillary data structure (hashmap, set, etc.)

    • longest substring with at most k distinct characters
    • string permutation


  • Everything is grouped in a sequence

B. Leetcode problems

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.


Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Key ideas:

  • The auxillary data structure is a min_price variable
    • We keep track of the minimum price we have seen so far
    • We can use this to calculate the maximum profit we can make

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

        profit = 0
        minBuy = prices[0]

        for sellP in prices:
            profit = max(profit, sellP-minBuy)
            minBuy = min(minBuy, sellP)

        return profit

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.


Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3.

Key ideas:

  • Move the forward pointer of the window with the outer for loop
    • Maintain a set of the characters in the window
    • At any point, keep removing the character at the beginning of the window until the window is valid
      • Increment the window size by 1 for each removal
  • Keep track of the maximum length of the substring

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

        if len(s) == 0:
            return 0

        start = 0
        seen = set()
        maxlen = 1

        for i in range(len(s)):

            while s[i] in seen:
                start += 1

            maxlen = max(maxlen, len(seen))

        return maxlen

567. Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.


Input: s1=“ab” s2=“eidbaooo”
Output: true Explanation: s2 contains one permutation of s1 (“ba”).

Key ideas:

  • Checking permutation of one string in another is essentially checking the anagram in the window
    • run a loop while the right pointer is less than the length of s2
      • Use a hashmap to keep track of the characters in the window
      • If it is equal to the hashmap of s1, return true
      • Increment both right and left pointers by 1

from collections import Counter

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

        if len(s1) > len(s2):
            return False

        l = 0
        r = len(s1)
        s1Count = Counter(s1)

        while r <= len(s2):
            if s1Count == Counter(s2[l:r]):
                return True
            l += 1
            r += 1

        return False

76. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.


Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC” Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Key ideas:

  • create a hashmap of the characters in t which are the expected characters in a window.
  • Use a hashmap to keep track of the characters in the window
    • use left and right pointers to handle the length of window
    • use seen to keep track of the expected characters in the window
      • if seen is equal to the length of hashmap of t then start moving the left pointer
      • maintain the minimum length of the window and its string

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

        m,n = len(s), len(t)

        if n == 0:
            return ""

        refCharCount = dict(collections.Counter(t))
        expectedKeyChars = len(refCharCount)

        seen = 0
        windowMap = {} # contains the character count in the current window

        l = 0
        minMatch, minlen = [0,0], float("inf")

        for r in range(m):

            c = s[r]

            windowMap[c] = windowMap.get(c, 0) + 1

            if c in refCharCount and windowMap[c] == refCharCount[c]:
                seen += 1

            while l <= r and seen == expectedKeyChars:

                if minlen > r-l+1:
                    minMatch = s[l:r+1]
                    minlen = min(minlen, r-l+1)

                windowMap[s[l]] -= 1

                # reduce seen if the removed character is in refCharCount
                if s[l] in refCharCount and windowMap[s[l]] < refCharCount[s[l]]:
                    seen -= 1

                l += 1

        if minlen == float("inf"):
            return ""

        return minMatch

239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.


Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Key ideas:

  • Maintain a queue which monotonically decreasing; first element is always the maximum

    • Before adding the element, keep popping till the element is greater than the current number to be added
      • Add the index of the element to the queue
    • If the first element is out of the window, remove it
    • If the right index is greater than k-1, append the first element of the queue to the result
      • Increment the left index by 1
  • deque was used as popleft and pop are O(1) operations


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

        result = []
        l = 0

        q = collections.deque([])

        for r in range(len(nums)):

            while q and nums[q[-1]] < nums[r]:


            if l > q[0]:

            if r >= k-1:

        return result

424. Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.


Input: s = “ABAB”, k = 2
Output: 4 Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.

Key ideas:

  • window is maintained with left and right pointers

  • Maintain a dict to keep track of the character count in the window

  • Find the most frequent character in the window

    • If the following condition is satisfied; move the left pointer and reduce the count of that respective character $$\text{window length} - \text{count of most freq char} \gt k$$
  • check max length of the window and update the result


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:

        freq = collections.defaultdict(int)
        l,r = 0,0

        result = 0

        while r < len(s):

            freq[s[r]] += 1

            maxfreq = max(freq.values())

            if r-l+1 - maxfreq > k:
                freq[s[l]] -= 1
                l += 1

            result = max(result, r-l+1)

            r += 1

        return result