0Pricing
DSA Interview Prep · Lesson

Sliding Window for Substrings

Implement the variable-size sliding window to find the longest substring without repeating characters and the minimum window containing all target characters.

Sliding Window for Substrings is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

The Sliding Window Concept

A sliding window maintains a subarray (or substring) between a left and right pointer. Instead of recomputing properties of every possible subarray from scratch in O(n²), the window expands right by adding one element and contracts left by removing one element, maintaining a running state in O(1) per step. The result is an O(n) algorithm. The window is called 'sliding' because it moves forward through the array without going backward.

# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
    window_sum = sum(nums[:k])  # initial window
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i]       # add new right
        window_sum -= nums[i - k]   # remove old left
        best = max(best, window_sum)
    return best

print(max_sum_window([2,1,5,1,3,2], 3))  # 9  ([5,1,3])

Fixed vs Variable Window Size

There are two flavours of sliding window. In a fixed-size window, both pointers advance at the same pace and the window always has exactly k elements. In a variable-size window, the right pointer expands greedily and the left pointer contracts only when the window violates a constraint. Variable-size windows solve problems like 'longest substring without repeating characters' where the optimal window size is unknown ahead of time.

# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
    from collections import defaultdict
    freq = defaultdict(int)
    left = 0
    best = 0
    for right in range(len(s)):
        freq[s[right]] += 1
        while len(freq) > k:    # window invalid: shrink
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_k_distinct('eceba', 2))   # 3  ('ece')
print(longest_k_distinct('aa', 1))      # 2

Longest Substring Without Repeating

The most famous variable sliding window problem. Use a set to track characters in the current window. Expand right; when a duplicate is found, shrink from the left until the duplicate is removed. A faster version uses a hash map storing the latest index of each character, allowing the left pointer to jump past the duplicate in one step rather than inching forward.

def length_of_longest_substring(s):
    char_idx = {}  # char -> last seen index
    left = 0
    best = 0
    for right, c in enumerate(s):
        if c in char_idx and char_idx[c] >= left:
            left = char_idx[c] + 1  # jump past duplicate
        char_idx[c] = right
        best = max(best, right - left + 1)
    return best

print(length_of_longest_substring('abcabcbb'))  # 3 ('abc')
print(length_of_longest_substring('bbbbb'))     # 1
print(length_of_longest_substring('pwwkew'))    # 3 ('wke')

Minimum Window Substring

Given strings s and t, find the smallest window in s containing all characters of t. Use two frequency maps: need (characters required) and have (characters in current window meeting the requirement). Track how many unique characters in t are satisfied (formed counter). Expand right to include characters; when all of t is covered, shrink left to minimise the window. O(|s| + |t|) time.

from collections import Counter

def min_window(s, t):
    if not t or not s: return ''
    need = Counter(t)
    have = {}
    formed = 0
    required = len(need)
    left = 0
    best = float('inf'), 0, 0
    for right, c in enumerate(s):
        have[c] = have.get(c, 0) + 1
        if c in need and have[c] == need[c]:
            formed += 1
        while formed == required:
            if right - left + 1 < best[0]:
                best = right - left + 1, left, right
            have[s[left]] -= 1
            if s[left] in need and have[s[left]] < need[s[left]]:
                formed -= 1
            left += 1
    return s[best[1]:best[2]+1] if best[0] != float('inf') else ''

print(min_window('ADOBECODEBANC', 'ABC'))  # 'BANC'

Sliding Window Template

Most variable sliding window problems share a template: expand right to include the new character, update the window state, check validity, and if invalid shrink from the left until valid again. The key insight is that the left pointer only moves forward — it never goes backward — so the total work across all shrink steps is O(n). The window visits each element at most twice (once added, once removed).

def sliding_window_template(s, condition_check, update_state, remove_state):
    """
    Generic sliding window skeleton.
    Adapt condition_check, update_state, remove_state per problem.
    """
    left = 0
    state = {}  # or whatever state you need
    best = 0
    for right in range(len(s)):
        update_state(state, s[right])      # expand window
        while not condition_check(state):  # window invalid
            remove_state(state, s[left])   # shrink window
            left += 1
        best = max(best, right - left + 1)
    return best

Permutation in String

Check if any permutation of pattern p exists as a substring of s. A permutation check is equivalent to a window with the same character frequency as p. Maintain a sliding window of exactly len(p) characters and compare frequency counts. Comparing entire Counter objects each step is O(26) (constant for lowercase English), giving O(n × 26) = O(n) overall.

from collections import Counter

def check_inclusion(p, s):
    if len(p) > len(s): return False
    need  = Counter(p)
    window = Counter(s[:len(p)])
    if need == window: return True
    for right in range(len(p), len(s)):
        left = right - len(p)
        window[s[right]] += 1
        window[s[left]]  -= 1
        if window[s[left]] == 0:
            del window[s[left]]
        if window == need:
            return True
    return False

print(check_inclusion('ab', 'eidbaooo'))  # True ('ba')
print(check_inclusion('ab', 'eidboaoo'))  # False

Anagram Substrings: Count All

Find all starting indices of p's anagrams in s. This is the same fixed-window technique as permutation-in-string, but instead of returning True on the first match, we collect all matching positions. The window size is fixed at len(p); we slide it across s and compare frequency counts at each step.

from collections import Counter

def find_anagrams(s, p):
    result = []
    need = Counter(p)
    k = len(p)
    window = Counter(s[:k])
    if window == need:
        result.append(0)
    for right in range(k, len(s)):
        window[s[right]] += 1
        left_char = s[right - k]
        window[left_char] -= 1
        if window[left_char] == 0:
            del window[left_char]
        if window == need:
            result.append(right - k + 1)
    return result

print(find_anagrams('cbaebabacd', 'abc'))  # [0, 6]

Longest Substring with At Most 2 Distinct

A sliding window variant: find the longest substring containing at most 2 distinct characters. Maintain a frequency map of characters in the current window. When the map exceeds 2 entries, move the left pointer right (decrement frequency, delete if zero) until the constraint is restored. This is a special case of 'at most k distinct' with k=2.

def longest_substring_two_distinct(s):
    from collections import defaultdict
    freq = defaultdict(int)
    left = 0
    best = 0
    for right, c in enumerate(s):
        freq[c] += 1
        while len(freq) > 2:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_substring_two_distinct('eceba'))     # 3  ('ece')
print(longest_substring_two_distinct('ccaabbb'))   # 5  ('aabbb')

Sliding Window Maximum

Find the maximum in every window of size k. A brute-force check of each window's max takes O(n×k). The optimal approach uses a monotonic deque of indices: maintain a decreasing deque so the front is always the index of the current window maximum. Remove indices from the front when they leave the window, and remove indices from the back when a larger element enters. O(n) time total.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # stores indices, decreasing values
    result = []
    for i, n in enumerate(nums):
        # Remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Maintain decreasing order
        while dq and nums[dq[-1]] < n:
            dq.pop()
        dq.append(i)
        if i >= k - 1:  # window is full
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

When to Use Sliding Window

Reach for the sliding window when you see:

  • Substring / subarray with a constraint (max length, sum = k, at most k distinct)
  • Fixed window size with an aggregation (max, sum, frequency)
  • Contiguous range questions (not arbitrary subsets)
Do NOT use sliding window for: non-contiguous selections, problems requiring all permutations (use backtracking), or problems where the window cannot maintain state incrementally. The key test: can you update state in O(1) when adding/removing one element?

# Recognising sliding window problems:

# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
    s = sum(nums[:k])
    best = s
    for i in range(k, len(nums)):
        s += nums[i] - nums[i-k]
        best = max(best, s)
    return best / k

print(max_avg([1,12,-5,-6,50,3], 4))  # 12.75

# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
    left = s = 0
    best = float('inf')
    for right, n in enumerate(nums):
        s += n
        while s >= target:
            best = min(best, right - left + 1)
            s -= nums[left]; left += 1
    return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3]))  # 2

Counting Valid Windows: At Most K

Some problems ask for the number of subarrays satisfying a condition. A useful trick: count subarrays with at most k distinct characters, then subtract to get exactly k: exactly(k) = at_most(k) - at_most(k-1). Each call to at_most is O(n), giving O(n) total. The at_most function counts windows where the number of distinct characters does not exceed k by summing right - left + 1 (all valid left endpoints for each right).

from collections import defaultdict

def subarrays_at_most_k(s, k):
    freq = defaultdict(int)
    left = 0
    count = 0
    for right, c in enumerate(s):
        freq[c] += 1
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0: del freq[s[left]]
            left += 1
        count += right - left + 1  # all valid windows ending at right
    return count

def subarrays_exactly_k(s, k):
    return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)

print(subarrays_exactly_k('araaci', 2))  # 9

Quick Check

Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.

Lesson Recap

In this lesson you learned: the sliding window eliminates O(n²) by maintaining a running window state that updates in O(1) as elements enter and leave, fixed-size windows advance both pointers at the same pace; variable-size windows expand right greedily and contract left only when a constraint is violated, and minimum window substring and permutation-in-string both use frequency-map window state with a counter tracking how many required characters are currently satisfied. Next up we explore anagrams and character frequency maps.

Frequently asked questions

Is the “Sliding Window for Substrings” lesson free?

Yes — the full text of “Sliding Window for Substrings” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.

What will I learn in “Sliding Window for Substrings”?

Implement the variable-size sliding window to find the longest substring without repeating characters and the minimum window containing all target characters. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start DSA Interview Prep?

No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Sliding Window for Substrings” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this DSA Interview Prep lesson?

Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

  1. Python String API for Interviews
  2. Sliding Window for Substrings
  3. Anagrams and Character Frequency Maps
  4. String Encoding, Reversal, and Palindromes
← Back to DSA Interview Prep