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

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

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 = 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
code


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

profit = 0

for sellP in prices:

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
• 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

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, return true
• Increment both right and left pointers by 1
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 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
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 > 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.

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

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 >= k-1:
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 r-l+1 - maxfreq > k:
freq[s[l]] -= 1
l += 1

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

r += 1

return result



Previous
Next