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

Fixed length variant
 max sum of subarray of size k

Dynamic variant
 smallest sum that is greater than or equal to a target

Dynamic variant w/ Auxillary data structure (hashmap, set, etc.)
 longest substring with at most k distinct characters
 string permutation
Commonalities:
 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
.
Example:
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 = 61 = 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
code
class Solution:
def maxProfit(self, prices: List[int]) > int:
profit = 0
minBuy = prices[0]
for sellP in prices:
profit = max(profit, sellPminBuy)
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.
Example:
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
 Maintain a
 Keep track of the maximum length of the substring
code
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:
seen.remove(s[start])
start += 1
seen.add(s[i])
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
.
Example:
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
, returntrue
 Increment both right and left pointers by 1
 run a loop while the right pointer is less than the length of
code
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.
Example:
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
andright
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 oft
then start moving the left pointer  maintain the minimum length of the window and its string
 if
 use
code
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 > rl+1:
minMatch = s[l:r+1]
minlen = min(minlen, rl+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.
Example:
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
k1
, append the first element of the queue to the result Increment the left index by 1
 Before adding the element, keep popping till the element is greater than the current number to be added

deque
was used aspopleft
andpop
areO(1)
operations
code
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]:
q.pop()
q.append(r)
if l > q[0]:
q.popleft()
if r >= k1:
result.append(nums[q[0]])
l+=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.
Example:
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
Code
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 rl+1  maxfreq > k:
freq[s[l]] = 1
l += 1
result = max(result, rl+1)
r += 1
return result