Introduction
Often times in string or array problems, we want an optimal subarray or substring that satisfies some properties (or the count of such subarrays). Of course, we can brute force a solution in O(n²) time by comparing all {n choose 2} subarrays/substrings (choose a start and end index out of n indices), however this won't allow you to pass the interview.
We can often leverage Sliding Windows to optimize to a linear time O(n) solution.
Note that sliding window is basically another form of two pointers, where we initialize both pointers at index 0.
Similar to binary search, the template boils down to a few factors:
1. MAX or MIN template
2. Data structure for window (commonly frequency map, or integer)
3. While loop condition?
4. Update res logic
Given these items, you should know what the code looks like!
When Can We Use Sliding Window?
It's actually very similar to binary search. When the substrings [l,r] for all fixed l, are monotonic functions over r.
Ie. as we increase r: we have …TTTTFFFF… (max template), or …FFFFTTTT… (min template)
Where a boolean is the mapping of a substring: is_valid(s[l,r]) -> {T,F}
IMPORTANT: There is also a relationship between the is_valid() function outputs for substrings:
For Max template: If is_valid(s) is True, then any substring of s has is_valid(substring) = True as well. And when is_valid(s) is False, any superstring of s has is_valid = False.
For Min template: If is_valid(s) is False, then any substring of s has is_valid(substring) = False as well. And when is_valid(s) is True, any superstring of s has is_valid = True.
Example: Longest substring with at most 2 distinct characters
s = 'abcd'
- Fix l = 0: R=0: is_valid('a')=T, R=1: is_valid('ab')=T, R=2: is_valid('abc')=F, R=3: is_valid('abcd')=F
- Fix l = 1: R=1: is_valid('b')=T, R=2: is_valid('bc')=T, R=3: is_valid('bcd')=F
- Fix l = 2: R=2: is_valid('c')=T, R=3: is_valid('cd')=T
- Fix l = 3: R=3: is_valid('d')=T
- Since is_valid is monotonic for all fixed l, we can apply the Max template.
Templates
There are 2 templates: Max and Min (similar to Binary Search).
If we are given a string of lowercase english letters, len(freq) <= 26 so we can say time is O(n) and space is O(1).
O(n * len(freq))O(len(freq))Max Template - Find Maximum Substring
Use when: Small substrings are VALID by default, we want the longest valid substring.
Pattern: Move right until INVALID, then move left until VALID again. Update res outside the while loop (when valid).
TTTTFFFF... (monotonically decreasing validity)
def findMaxSubstring(self, s: str):
freq = Counter() # window
n = len(s)
l = 0 # left pointer
res = 0
for r in range(n): # move right while window is VALID
freq[s[r]] += 1 # add s[r] to window
while is_valid(freq) == False: # condition when window is INVALID
freq[s[l]] -= 1 # move left to try to make it VALID again
if freq[s[l]] == 0: del freq[s[l]]
l += 1
# window is VALID here - update res
res = max(res, r - l + 1)
return resMin Template - Find Minimum Substring
Use when: Small substrings are INVALID by default, we want the shortest valid substring.
Pattern: Move right until VALID, then move left until INVALID again. Update res inside the while loop (when valid).
FFFFTTTT... (monotonically increasing validity)
def findMinSubstring(self, s: str):
freq = Counter() # window
n = len(s)
l = 0
res = inf
for r in range(n): # move right while INVALID
freq[s[r]] += 1 # add s[r] to window
while is_valid(freq) == True: # condition when VALID
res = min(res, r - l + 1) # update res (we're valid!)
# move left to try to make it INVALID again
freq[s[l]] -= 1
if freq[s[l]] == 0: del freq[s[l]]
l += 1
# window is INVALID here
return resMax Template Problems
Problems where we want the longest/maximum valid substring. Small substrings are valid by default.
01Longest Substring with At Most K Distinct CharactersMedium
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
def lengthOfLongestSubstringKDistinct(self, s: str, k: int):
n, l, freq, res = len(s), 0, Counter(), 0
for r in range(n):
freq[s[r]] += 1
while len(freq) > k:
freq[s[l]] -= 1
if freq[s[l]] == 0: del freq[s[l]]
l += 1
res = max(res, r - l + 1)
return resO(n)O(k)This function is monotonic: TTTTTFFFF. Small strings are valid (have at most k distinct chars), large strings invalid.
Key points:
1. Max template
2. Counter()
3. Invalid condition: len(freq) > k
4. Res = max(res, r-l+1)
02Fruit Into BasketsMedium
You are given 2 fruit baskets that can fit unlimited fruits of a single type. You want the maximum number of fruit you can pick, from a consecutive row of fruits.
def totalFruit(self, fruits: List[int]) -> int:
n, l, freq, res = len(fruits), 0, Counter(), 0
for r in range(n):
freq[fruits[r]] += 1
while len(freq) > 2:
freq[fruits[l]] -= 1
if freq[fruits[l]] == 0: del freq[fruits[l]]
l += 1
res = max(res, r - l + 1)
return res
# Or simply:
# return lengthOfLongestSubstringKDistinct(fruits, 2)O(n)O(1)This is exactly the same as Q340 with k = 2. Note: fruits is a list of ints, not a string, but you can easily adapt the template.
03Longest Substring Without Repeating CharactersMedium
Given a string s, find the length of the longest substring without repeating characters.
def lengthOfLongestSubstring(self, s: str) -> int:
n, l, res, freq = len(s), 0, 0, Counter()
for r in range(n):
freq[s[r]] += 1
while freq[s[r]] >= 2:
freq[s[l]] -= 1
l += 1
res = max(res, r - l + 1)
return resO(n)O(26) = O(1)The function is monotonic: TTTFFFF. We check if the current character s[r] is already present in our window. If it is, increment the left pointer until we get rid of that previous instance.
04Max Consecutive Ones IIIMedium
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
def longestOnes(self, nums: List[int], k: int) -> int:
n, l, num_0, res = len(nums), 0, 0, 0
for r in range(n):
num_0 += nums[r] == 0
while num_0 > k:
num_0 -= nums[l] == 0
l += 1
res = max(res, r - l + 1)
return resO(n)O(1)In this case, our window is not a frequency map, rather an integer. num_0 represents the frequency of 0's in our window. When it is > k, this means we can no longer flip all the 0's in the window, so this is invalid.
05Continuous SubarraysMedium
A subarray of nums is called continuous if for each pair of indices i1, i2 in the subarray, |nums[i1] - nums[i2]| <= 2.
Return the total number of continuous subarrays.
from sortedcontainers import SortedList
def continuousSubarrays(self, nums: List[int]) -> int:
n = len(nums)
l = 0
res = 0
window = SortedList()
for r in range(n):
window.add(nums[r])
while window and window[-1] - window[0] > 2:
window.discard(nums[l])
l += 1
# [l,r] works - count all subarrays ending at r
res += r - l + 1
return resO(n log n)O(n)Think of SortedList as a sorted list of numbers. window.add(3) maintains sorted order. window.discard(5) removes element. Operations take O(log n) time.
Key insight: res += r-l+1 because if [l,r] works, any subarray that ends at index r and starts at index i: l <= i <= r also works.
Min Template Problems
Problems where we want the shortest/minimum valid substring. Small substrings are invalid by default.
01Minimum Size Subarray SumMedium
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
l = 0
res = inf
window_sum = 0
for r in range(n):
window_sum += nums[r]
while window_sum >= target:
res = min(res, r - l + 1)
window_sum -= nums[l]
l += 1
return res if res != inf else 0O(n)O(1)Monotonic function: FFFFFTTTTT. If sum < target, any smaller subarray is also < target. And once >= target, any larger subarray is also (because array is positive integers only!).
The idea: slide right until we reach the first valid subarray. Then while still valid, slide left and update inside the while loop.
02Minimum Consecutive Cards to Pick UpMedium
Given an integer array cards where cards[i] represents the value of the ith card. A pair of cards are matching if they have the same value.
Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards. If impossible, return -1.
def minimumCardPickup(self, cards: List[int]) -> int:
n, l, freq, res = len(cards), 0, Counter(), float('inf')
for r in range(n):
freq[cards[r]] += 1
while freq[cards[r]] == 2:
res = min(res, r - l + 1)
freq[cards[l]] -= 1
l += 1
return res if res != float('inf') else -1O(n)O(n)Straightforward min template. We are valid once we have a repeating card (freq == 2).
03Number of Substrings Containing All Three CharactersMedium
Given a string s consisting only of characters a, b and c. Return the number of substrings containing at least one occurrence of all these characters a, b and c.
def numberOfSubstrings(self, s: str) -> int:
freq = Counter()
n = len(s)
l = 0
res = 0
for r in range(n):
freq[s[r]] += 1
while len(freq) == 3:
res += n - r # all subarrays with end index [r, n-1] work
freq[s[l]] -= 1
if freq[s[l]] == 0: del freq[s[l]]
l += 1
return resO(n)O(1)Min template (FFFTTT). Once we are valid, any subsequent substring is valid.
Key insight: res += n-r, since all subarrays that start at index l and end at some index between [r, n-1] work (because of monotonicity).
04Minimum Window SubstringHard
Given two strings s and t, 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 "".
# Naive O(26*m + n) solution
def minWindow(self, big: str, small: str) -> str:
m, n = len(big), len(small)
freq_small = Counter(small)
window_freq = Counter()
l = 0
min_length = inf
res = []
def check(f1, f2):
for b in f2:
if f1[b] < f2[b]: return False
return True
for r in range(m):
if big[r] in freq_small:
window_freq[big[r]] += 1
while check(window_freq, freq_small):
if r - l + 1 < min_length:
res = [l, r]
min_length = r - l + 1
if big[l] in freq_small:
window_freq[big[l]] -= 1
l += 1
return big[res[0]:res[1]+1] if res else ""
# Optimized O(m+n) solution - INTERVIEW READY
def minWindow(self, big: str, small: str) -> str:
m, n = len(big), len(small)
freq_small = Counter(small)
l = 0
counter = 0
min_length = inf
res = []
for r in range(m):
if big[r] in freq_small:
freq_small[big[r]] -= 1
if freq_small[big[r]] >= 0:
counter += 1
while counter == n:
if r - l + 1 < min_length:
res = [l, r]
min_length = r - l + 1
if big[l] in freq_small:
freq_small[big[l]] += 1
if freq_small[big[l]] > 0:
counter -= 1
l += 1
return big[res[0]:res[1]+1] if res else ""O(m+n)O(26) = O(1)This is a really hard problem. The optimized solution removes the window counter and just updates freq_small, along with an integer counter that records how many characters in small we currently have in our window. This shaves our subset check() in the while loop from O(26) to O(1).
Fixed Sliding Window
There is a variant of sliding windows for a fixed window size of k. Since there are only n-k+1 subarrays of length k, it is simpler to get an O(n) solution - we can simply brute force.
Space complexity: O(size_of(window)), generally O(1).
Correctness: Obvious, since this is brute force - we look at all subarrays of length k.
Fixed Window Template
The intuition is that we first fill up the window. Once we get our first full window of length k at index i = k-1, we then update res if the window is valid. Index i represents the right index of the window, and thus index i-(k-1) represents the left index.
def fixedSlidingWindow(self, nums: List[int], k: int) -> int:
n = len(nums)
res = 0 # integer or array, etc.
window = 0 # freq_map, int, etc - some representation
for i in range(n):
# Update window with new right at index i
window = update_window_add(window, nums[i])
if i >= k - 1:
# If this window of size k is valid, count it
if is_valid(window):
res = update_res(res)
# Update window by removing old left at index i-(k-1)
window = update_window_remove(window, nums[i-(k-1)])
return res01Substrings of Size Three with Distinct CharactersEasy
A string is good if there are no repeated characters. Given a string s, return the number of good substrings of length three in s.
def countGoodSubstrings(self, s: str) -> int:
freq = Counter()
n = len(s)
res = 0
k = 3
for i in range(n):
freq[s[i]] += 1
if i >= k - 1:
if len(freq) == 3: # no repeated chars
res += 1
freq[s[i-(k-1)]] -= 1
if freq[s[i-(k-1)]] == 0:
del freq[s[i-(k-1)]]
return resO(n)O(1)Window: Counter(). Valid: len(freq) == 3 (because the substring has fixed length 3, if we have a counter of length 3, this means we have no repeated chars).
02Find the K-Beauty of a NumberEasy
The k-beauty of an integer num is defined as the number of substrings of num when it is read as a string that meet the following conditions:
• It has a length of k.
• It is a divisor of num.
# Simple approach
def divisorSubstrings(self, num: int, k: int) -> int:
s = str(num)
n = len(s)
res = 0
for i in range(n):
if i >= k - 1:
window = int(s[i-(k-1):i+1])
if window != 0 and num % window == 0:
res += 1
return res
# Optimized - compute window on the fly
def divisorSubstrings(self, num: int, k: int) -> int:
s = str(num)
n = len(s)
res = 0
window = 0
pow_ = 10 ** (k - 1)
for i in range(n):
window = 10 * window + int(s[i])
if i >= k - 1:
if window != 0 and num % window == 0:
res += 1
window %= pow_
return resO(n)O(1)Window = int(s[i-(k-1):i+1]). Valid: window != 0 and num % window == 0.
03K Radius Subarray AveragesMedium
The k-radius average for a subarray centered at index i with radius k is the average of all elements between indices i-k and i+k (inclusive). Build and return an array where each element is the k-radius average, or -1 if there aren't enough elements.
def getAverages(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
res = [-1] * n
sum_ = 0
for i in range(n):
sum_ += nums[i]
if i >= 2 * k:
res[i - k] = sum_ // (2 * k + 1)
sum_ -= nums[i - 2 * k]
return resO(n)O(n)Note: k in this case refers to one side of the array, so the window is of size 2k+1. We want to update index i-k in res, because that's the midpoint index of the window.
04Sliding Window MedianHard
Given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. Return the median array for each window.
from sortedcontainers import SortedList
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
n = len(nums)
window = SortedList()
res = []
for i in range(n):
window.add(nums[i])
if i >= k - 1:
if k % 2 == 1:
res.append(window[k // 2])
else:
res.append((window[k // 2 - 1] + window[k // 2]) / 2)
window.discard(nums[i - (k - 1)])
return resO(n log k)O(k)Even though this is a 'hard' problem, it's actually pretty straightforward.
Window = SortedList() because we want access to the median fast.
- When k is odd (like 3), the median is at index k//2
- When k is even (like 4), the median is the average of index k//2-1 and k//2
05Sliding Window MaximumHard
Given an array of integers nums and an integer k. There is a sliding window of size k which is moving from left to right. Return the max sliding window.
from sortedcontainers import SortedList
# O(n log k) sorted list solution
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
window = SortedList()
res = []
for i in range(n):
window.add(nums[i])
if i >= k - 1:
res.append(window[-1]) # max is rightmost
window.discard(nums[i - (k - 1)])
return resO(n log k)O(k)Window = SortedList() because we want access to the max fast. All windows are valid - just append the max, which is window[-1] (rightmost element).
Note: There is actually a more optimal O(n) solution using monotonic deque, covered in the Monotonic Stack chapter.
Anagram / Permutation Problems
These problems combine fixed sliding window with frequency counting to find anagrams or permutations.
01Permutation in StringMedium
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.
def checkInclusion(self, s1: str, s2: str) -> bool:
k = len(s1)
window = Counter(s1)
count = 0
set_ = set(s1)
for i in range(len(s2)):
if s2[i] in set_:
window[s2[i]] -= 1
if window[s2[i]] == 0:
count += 1
if i >= k - 1:
if count == len(set_):
return True
if s2[i - (k - 1)] in set_:
window[s2[i - (k - 1)]] += 1
if window[s2[i - (k - 1)]] == 1:
count -= 1
return FalseO(n)O(26) = O(1)We track how many characters have been fully matched (count). When count equals the number of unique characters in s1, we've found a permutation.
02Find All Anagrams in a StringMedium
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
def findAnagrams(self, s2: str, s1: str) -> List[int]:
k = len(s1)
window = Counter(s1)
count = 0
set_ = set(s1)
res = []
for i in range(len(s2)):
if s2[i] in set_:
window[s2[i]] -= 1
if window[s2[i]] == 0:
count += 1
if i >= k - 1:
if count == len(set_):
res.append(i - (k - 1))
if s2[i - (k - 1)] in set_:
window[s2[i - (k - 1)]] += 1
if window[s2[i - (k - 1)]] == 1:
count -= 1
return resO(n)O(26) = O(1)Same as Q567 but we collect all starting indices instead of returning True on first match.
At Most K Template and Fixed 2D Windows
When you want to solve an exactly k problem using sliding window and the logic seems challenging - often times it is easier to compute using at most k or at least k.
Formula: Exactly k = At most(k) - At most(k-1)
OR: Exactly k = At least(k) - At least(k+1)
This section also includes the source's fixed 2D sliding-window example, where each k×k submatrix is treated as a window over grid values.
01Binary Subarrays With Sum (AtMost K)Medium
Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum equal to goal.
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
n = len(nums)
def atMostK(k):
if k == -1: return 0
l = 0
window_sum = 0
res = 0
for r in range(n):
window_sum += nums[r]
while window_sum > k:
window_sum -= nums[l]
l += 1
res += r - l + 1
return res
return atMostK(goal) - atMostK(goal - 1)O(n)O(1)This only works because nums[i] >= 0. If negatives were allowed, we can't use sliding window.
Note: This can also be solved using hashmap (see Arrays and Hashing chapter).
02Count Number of Nice Subarrays (AtMost K)Medium
Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.
Return the number of nice sub-arrays.
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
def atMostK(k):
n, l, num_odd, res = len(nums), 0, 0, 0
for r in range(n):
num_odd += nums[r] % 2
while num_odd > k:
num_odd -= nums[l] % 2
l += 1
res += r - l + 1 # r-l+1 subarrays end at index r
return res
return atMostK(k) - atMostK(k - 1)O(n)O(1)This problem can also be solved using subarray sums = k (see Two Sum Like section in hashing chapter).
03Subarrays with K Different IntegersHard
Given an integer array nums and an integer k, return the number of good subarrays of nums.
A good array is an array where the number of different integers in that array is exactly k.
def subarraysWithKDistinct(self, s: List[int], k: int) -> int:
def atMostK(k: int) -> int:
n = len(s)
freq = Counter()
l = 0
res = 0
for r in range(n):
freq[s[r]] += 1
while len(freq) == k + 1:
freq[s[l]] -= 1
if freq[s[l]] == 0:
del freq[s[l]]
l += 1
res += r - l + 1
return res
return atMostK(k) - atMostK(k - 1)O(n)O(k)This is a hard problem. But it seems so easy right? This is the power of templates and thinking through patterns.
04Minimum Absolute Difference in Sliding SubmatrixMedium
For every k×k submatrix, find minimum absolute difference between any two distinct values.
from itertools import pairwise
def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:
m, n = len(grid), len(grid[0])
res = [[0] * (n - k + 1) for _ in range(m - k + 1)]
for i in range(m - k + 1):
for j in range(n - k + 1):
values = set()
for ii in range(k):
for jj in range(k):
values.add(grid[i + ii][j + jj])
ordered = sorted(values)
res[i][j] = min((b - a for a, b in pairwise(ordered)), default=0)
return resO(m * n * k² log k)O(k²)Fixed 2D sliding window. The problem asks for distinct values, so duplicates must not create a false difference of 0. The source shows a direct set-based version and mentions optimizing with a SortedSet plus frequencies.
Summary
Sliding window is a powerful technique that can optimize problems from O(n²) to O(n). It comes with the same monotonic requirements and min/max templates as Binary Search does.
Think of sliding window when:
1. Finding an optimal substring (minimal or maximal to some condition)
2. Counting the number of valid/invalid substrings
3. The validity function is monotonic over the window size
Key Decision Points:
1. Max or Min template? - What are you optimizing for?
2. Window data structure? - Counter, integer, SortedList?
3. Invalid/Valid condition? - What makes a window valid?
4. Update logic? - Inside or outside the while loop?