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 = 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_pricevariable- 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, 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.
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
forloop- Maintain a
setof 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
twhich are the expected characters in a window. - Use a hashmap to keep track of the characters in the window
- use
leftandrightpointers to handle the length of window - use
seento keep track of the expected characters in the window- if
seenis equal to the length of hashmap oftthen 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 > 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
- Before adding the element, keep popping till the element is greater than the current number to be added
-
dequewas used aspopleftandpopareO(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
dictto 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