Sliding Window
Maintain a window with left and right pointers. Expand right to include elements; shrink left when a constraint is violated. Find the longest/shortest substring or subarray satisfying a condition.
Given a string, find the length of the longest substring that contains no repeating characters. For example, in "abcabcbb" the answer is 3, because "abc" is the longest stretch where every character is unique.
The brute-force approach is straightforward: check every possible substring, and for each one, verify whether all characters are distinct. There are substrings, and checking each for uniqueness takes up to time, giving overall. You can improve the uniqueness check to amortized with a hash set, bringing it down to , but that is still far too slow for strings of length 100,000. We need a fundamentally different approach.
Instead of checking every substring independently, maintain a window defined by two pointers, left and right, that always satisfies the constraint (in this case, all characters in the window are unique). The algorithm works in two phases that alternate: expand the window by moving right forward, and shrink the window by moving left forward whenever the constraint is violated.
The reason this works is that once a window is invalid, no larger window starting at the same left position can possibly be valid. So instead of restarting from scratch, you slide the left edge forward until the window is valid again, then continue expanding.
Let's trace the algorithm on the string "abcabcbb" step by step. We maintain a set of characters in the current window.
We start with left = 0 and right = 0. We add 'a' to the set. Window: "a", length 1. Best so far: 1.
Move right to 1. Add 'b'. Window: "ab", length 2. Best: 2.
Move right to 2. Add 'c'. Window: "abc", length 3. Best: 3.
Move right to 3. The character is 'a', which is already in the set. The constraint is violated, so we shrink from the left. Remove 'a' at left = 0, advance left to 1. Now the set is {b, c} and 'a' is no longer a duplicate, so we add 'a' and stop shrinking. Window: "bca", length 3. Best: 3.
Move right to 4. Character is 'b', already in the set. Shrink: remove 'b' at left = 1, advance left to 2. Now add 'b'. Window: "cab", length 3. Best: 3.
Move right to 5. Character is 'c', already in the set. Shrink: remove 'c' at left = 2, advance left to 3. Add 'c'. Window: "abc", length 3. Best: 3.
Move right to 6. Character is 'b', already in the set. Shrink: remove 'a' at left = 3, advance left to 4. 'b' is still in the set. Remove 'b' at left = 4, advance left to 5. Now add 'b'. Window: "cb", length 2. Best still 3.
Move right to 7. Character is 'b', already in the set. Shrink: remove 'c' at left = 5, advance left to 6. Now add 'b'. Window: "b", length 1. Best still 3.
The answer is 3.
def lengthOfLongestSubstring(s):
char_set = set()
left = 0
best = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
best = max(best, right - left + 1)
return bestThe outer loop advances right one step at a time. The inner while loop shrinks from the left only when needed. After the while loop exits, the window is valid again, so we update the answer.
It might look like the nested loops make this , but consider what happens to each element. Every character is added to the set exactly once (when right reaches it) and removed from the set at most once (when left passes it). So the inner while loop does not execute n times per outer iteration. Across the entire run of the algorithm, left advances at most n times total. The total work is plus equals . This amortized argument is the key to understanding why sliding window algorithms are efficient.
LeetCode 76 asks you to find the smallest substring of s that contains all characters of t, given strings s and t. For example, with s = "ADOBECODEBANC" and t = "ABC", the answer is "BANC".
This is still a sliding window problem, but instead of looking for the longest valid window, you want the shortest. This flips where you update the answer. For "longest" problems, you update the answer after the shrink loop (when the window is valid and as large as possible). For "shortest" problems, you update the answer inside the shrink loop (each time you shrink and the window is still valid, it might be a new minimum).
With s = "ADOBECODEBANC" and t = "ABC", we need a window containing at least one A, one B, and one C. We track how many characters we still need.
Expand right through A, D, O, B, E, C. At this point the window "ADOBEC" (indices 0-5) contains all three target characters. Record length 6. Now shrink: remove A from left, move left to 1. The window "DOBEC" still needs an A, so it is no longer valid. Stop shrinking. Continue expanding.
Eventually the window reaches "CODEBA" and later "BANC". Each time the window becomes valid, we shrink as much as possible, recording the length each time the window is still valid. The shortest valid window turns out to be "BANC" with length 4.
from collections import Counter
def minWindow(s, t):
need = Counter(t)
missing = len(t)
left = 0
best_start, best_len = 0, float('inf')
for right in range(len(s)):
if need[s[right]] > 0:
missing -= 1
need[s[right]] -= 1
while missing == 0:
window_len = right - left + 1
if window_len < best_len:
best_start = left
best_len = window_len
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if best_len == float('inf') else s[best_start:best_start + best_len]Notice the structural difference: the answer update (if window_len < best_len) is inside the while loop. Every time we shrink and the window is still valid, we check whether it is a new minimum. This is the fundamental distinction between longest-window and shortest-window problems.
Consider LeetCode 340: given a string and an integer k, you must find the length of the longest substring with at most k distinct characters. For example, in "eceba" with k = 2, the answer is 3 ("ece").
The structure is identical to the no-repeats problem. You just change what "valid" means. Instead of checking for duplicates, you check whether the number of distinct characters exceeds k.
from collections import defaultdict
def lengthOfLongestSubstringKDistinct(s, k):
count = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
count[s[right]] += 1
while len(count) > k:
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
best = max(best, right - left + 1)
return bestThe window state is a frequency map, and the validity check is len(count) <= k. Everything else, the expand/shrink structure and the answer update outside the while loop, is the same template.
Every variable-size sliding window problem follows the same skeleton. You initialize left = 0 and some data structure tracking the window state. You iterate right across the input, updating the state. When the state violates the constraint, you shrink from the left until it is valid again. You update the answer either outside the shrink loop (for longest problems) or inside it (for shortest problems).
What changes between problems is just three things: the data structure tracking window state (a set, a frequency map, a counter), the condition that triggers shrinking (duplicate found, too many distinct characters, required characters not all present), and whether you want the longest or shortest valid window.
Once you internalize this template, you can solve a wide range of problems by simply identifying these three components. The algorithmic structure is always the same.
LeetCode 424 presents a variation: given a string and an integer k, find the length of the longest substring where you can replace at most k characters to make every character the same. For example, with s = "AABABBA" and k = 1, the answer is 4 ("AABA", replacing the B at index 3).
The key insight is that a window is valid when (window_size - max_freq) <= k, where max_freq is the count of the most frequent character in the window. The quantity window_size - max_freq tells you how many characters you would need to replace.
from collections import defaultdict
def characterReplacement(s, k):
count = defaultdict(int)
left = 0
max_freq = 0
best = 0
for right in range(len(s)):
count[s[right]] += 1
max_freq = max(max_freq, count[s[right]])
while (right - left + 1) - max_freq > k:
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return bestA subtle point: we never decrease max_freq when shrinking the window. This is safe because the answer can only improve when max_freq increases. If max_freq is stale (too high), the window just stays the same size or smaller, which does not produce a wrong answer. It only means we might not shrink as aggressively as we could.
For LeetCode 438, given a string s and a pattern p, you must find all start indices of p's anagrams in s. For example, with s = "cbaebabacd" and p = "abc", the answer is [0, 6] because "cba" and "bac" are both anagrams of "abc".
This is a fixed-size sliding window of length len(p). Strictly speaking, it is a cousin of the variable-size template covered here, but it shows how the same "track what is missing" bookkeeping carries over. Use a single need map initialized from p's counts, decrementing when a character enters the window and incrementing when it leaves. Track how many characters are still missing; the window is a valid anagram when that count reaches zero.
from collections import Counter
def findAnagrams(s, p):
if len(s) < len(p):
return []
need = Counter(p)
missing = len(p)
result = []
for right in range(len(s)):
if need[s[right]] > 0:
missing -= 1
need[s[right]] -= 1
if right >= len(p):
left_char = s[right - len(p)]
need[left_char] += 1
if need[left_char] > 0:
missing += 1
if missing == 0:
result.append(right - len(p) + 1)
return resultThis mirrors the minimum window substring approach but with a fixed window size, which eliminates the need for an inner while loop.
LeetCode 713 adds a twist: given an array of positive integers and a target k, you must count the number of contiguous subarrays whose product is strictly less than k. For example, with nums = [10, 5, 2, 6] and k = 100, the answer is 8.
The twist here is that instead of tracking the longest or shortest window, you count subarrays. When the window [left, right] is valid (product < k), every subarray ending at right that starts at or after left is also valid. There are exactly right - left + 1 such subarrays.
def numSubarrayProductLessThanK(nums, k):
if k <= 1:
return 0
product = 1
left = 0
count = 0
for right in range(len(nums)):
product *= nums[right]
while product >= k:
product //= nums[left]
left += 1
count += right - left + 1
return countThe count += right - left + 1 line is the key: for a valid window of size w ending at right, the new subarrays that end exactly at right are [left..right], [left+1..right], ..., [right..right], totaling w subarrays. We use integer division because the values are positive integers and we only care about the comparison with k.
With LeetCode 992, given an integer array and a target k, you must count the number of subarrays with exactly k distinct integers. For example, with nums = [1, 2, 1, 2, 3] and k = 2, the answer is 7.
Counting "exactly K" directly with a sliding window is awkward because removing an element from the left might not reduce the distinct count (there could be duplicates). The standard trick is to decompose "exactly K" into "at most K" minus "at most K - 1". Each "at most K" subproblem is a straightforward sliding window.
from collections import defaultdict
def subarraysWithKDistinct(nums, k):
def atMost(k):
count = defaultdict(int)
left = 0
result = 0
for right in range(len(nums)):
if count[nums[right]] == 0:
k -= 1
count[nums[right]] += 1
while k < 0:
count[nums[left]] -= 1
if count[nums[left]] == 0:
k += 1
left += 1
result += right - left + 1
return result
return atMost(k) - atMost(k - 1)Inside atMost, the logic is identical to the "at most K distinct characters" problem, and the counting trick is the same as the product-less-than-K problem: each valid window of size w contributes w new subarrays. The subtraction cancels out every subarray with fewer than k distinct values, leaving only those with exactly k.
Looking at LeetCode 2444, given an integer array and two integers minK and maxK, you must count the number of subarrays where the minimum value equals minK and the maximum value equals maxK. For example, with nums = [1, 3, 5, 2, 7, 5] and minK = 1, maxK = 5, the answer is 2.
This problem does not use the expand/shrink template. Instead, scan left to right and track three indices: the last position where you saw minK, the last position where you saw maxK, and the last position where you saw a value outside the range [minK, maxK]. For each position right, the number of valid subarrays ending there is determined by how far left you can start while still including both bounds and excluding out-of-range elements.
def countSubarrays(nums, minK, maxK):
last_min = -1
last_max = -1
last_bad = -1
count = 0
for right in range(len(nums)):
if nums[right] < minK or nums[right] > maxK:
last_bad = right
if nums[right] == minK:
last_min = right
if nums[right] == maxK:
last_max = right
valid_start = min(last_min, last_max)
count += max(0, valid_start - last_bad)
return countThe expression min(last_min, last_max) gives the earliest position that still lets both bounds be present. The subarray must start after last_bad to avoid out-of-range elements. So valid starting positions are last_bad + 1 through valid_start, giving valid_start - last_bad choices (or zero if that is negative). This runs in time with space.
Time complexity is for all standard variable-size sliding window problems. The argument is always the same: each element enters the window once and leaves at most once, so the total work across all iterations of the inner loop is . The outer loop also does work, giving total.
Space complexity is where k depends on the problem. For the no-repeats problem, k is the size of the character set (at most 26 for lowercase English letters, or 128 for ASCII). For the K distinct characters problem, k is the parameter K. For minimum window substring, k is the size of the target string's character set. In all cases, the space is bounded by the alphabet or the constraint, not the input size.
You're probably looking at a variable-size sliding window when:
Common templates:
right - left + 1 after each expansion. Example: Subarray Product Less Than K.Practice Problems (85)