Sliding Window Technique: A Practical Guide to Subarray and Substring Problems

Why sliding window shows up so often

If you’ve done even a few coding interviews, you’ve probably seen a problem that sounds like this:

• find the maximum sum subarray of size k
• locate the longest substring with no repeating characters
• count the number of subarrays that satisfy some condition
• find the smallest window that contains all required characters

These are all variations of the same idea: you do not need to recompute everything from scratch every time. Instead, you keep track of a window over the data and update it as the window moves.

That is why the sliding window technique matters. It turns many brute-force O(n^2) or O(n^3) solutions into clean O(n) solutions. In interviews, that is often the difference between a solution that works and one that scales well.

The pattern is especially useful for subarray and substring problems, where the input is linear and the answer depends on a contiguous section.

Problem statement: what sliding window solves

At a high level, sliding window helps when you are dealing with a contiguous range in an array or string.

Typical questions look like one of these:

• Fixed-size window: “Find the maximum sum of any subarray of length k.”
• Variable-size window: “Find the longest substring with at most k distinct characters.”
• Constraint-based window: “Find the minimum-length substring containing all characters from a set.”

The key signal is this: the problem asks for a contiguous segment, and the score for that segment can be updated incrementally when you move one step right.

Intuition: why the pattern works

Suppose you are looking at a window [left, right].

Instead of recalculating the answer for every possible interval, you keep a running state:

• counts of characters
• current sum
• number of distinct values
• number of matches against a target condition

When you move right forward, you add one element. When the window becomes invalid or too large, you move left forward and remove one element.

The important insight is that each element enters the window once and leaves once. That gives you linear time in many problems.

Two common forms

1. Fixed-size window

Use this when the window size is constant, such as k.

You expand the window until it reaches size k, then slide it forward one step at a time.

Example: maximum sum subarray of length k.

2. Variable-size window

Use this when the size changes based on a condition.

You expand the window to make progress, then shrink it while the condition is violated.

Example: longest substring without repeating characters.

Step-by-step approach

The sliding window template is usually:

1. Initialize left = 0 and some state for the current window.
2. Expand the window by moving right.
3. Update the state with the new element.
4. While the window is invalid, shrink from the left.
5. Record the answer when the window is valid.

The exact meaning of “valid” depends on the problem.

Example 1: Maximum sum subarray of size k

This is the classic fixed-size sliding window problem.

Problem

Given an integer array nums and an integer k, return the maximum sum of any contiguous subarray of length k.

Brute force idea

Check every length-k subarray and sum it. That costs O(nk).

Sliding window idea

Compute the sum of the first k elements. Then, as the window slides one step:

• subtract the element leaving the window
• add the new element entering the window

That gives you the new sum in O(1).

Python code

from typing import List

def max_sum_subarray_k(nums: List[int], k: int) -> int:
    if k <= 0 or k > len(nums):
        raise ValueError("k must be between 1 and len(nums)")

    window_sum = sum(nums[:k])
    max_sum = window_sum

    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

Walkthrough

For nums = [2, 1, 5, 1, 3, 2] and k = 3:

• first window: [2, 1, 5], sum = 8
• slide right: remove 2, add 1 → [1, 5, 1], sum = 7
• slide right: remove 1, add 3 → [5, 1, 3], sum = 9
• slide right: remove 5, add 2 → [1, 3, 2], sum = 6

The maximum is 9.

Why this matters

This pattern is one of the cleanest examples of sliding window. If you see a fixed-length subarray question, your first instinct should be: can I update the result incrementally?

Example 2: Longest substring without repeating characters

This is a variable-size window problem.

Problem

Given a string s, return the length of the longest substring without duplicate characters.

Why brute force is slow

You could check every substring and test whether it has duplicates, but that is expensive.

Sliding window idea

Track the characters currently in the window with a dictionary or set.

• Expand right one character at a time.
• If the new character already exists in the window, shrink from the left until the duplicate is removed.
• Update the best answer after each valid expansion.

Python code

def length_of_longest_substring(s: str) -> int:
    seen = set()
    left = 0
    best = 0

    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1

        seen.add(ch)
        best = max(best, right - left + 1)

    return best

Walkthrough

For s = "abcabcbb":

• window starts at "a", then "ab", then "abc"
• next character is a, which duplicates inside the window
• shrink from the left until a is removed
• continue this process

The best window length ends up being 3.

What to notice

You never move left backward. That is the core reason sliding window works efficiently. Each character is processed a small number of times, so the total work stays linear.

Example 3: Longest substring with at most k distinct characters

This is another common interview variation.

Problem

Given a string s and integer k, find the length of the longest substring containing at most k distinct characters.

Sliding window idea

Use a frequency map.

• Expand right and count characters.
• If the number of distinct characters becomes greater than k, shrink from the left.
• Track the maximum valid window length.

Python code

from collections import defaultdict

def longest_substring_at_most_k_distinct(s: str, k: int) -> int:
    if k == 0:
        return 0

    freq = defaultdict(int)
    left = 0
    best = 0

    for right, ch in enumerate(s):
        freq[ch] += 1

        while len(freq) > k:
            left_char = s[left]
            freq[left_char] -= 1
            if freq[left_char] == 0:
                del freq[left_char]
            left += 1

        best = max(best, right - left + 1)

    return best

Walkthrough

For s = "eceba" and k = 2:

• "e" → 1 distinct
• "ec" → 2 distinct
• "ece" → still 2 distinct
• "eceb" → 3 distinct, invalid
• shrink from left until valid again
• continue

The longest valid substring is "ece", length 3.

How to recognize sliding window in an interview

Look for these clues:

• the input is an array or string
• the answer depends on a contiguous segment
• you need a max/min length, sum, count, or condition over a range
• the problem can be updated by adding/removing one element at the boundary

Helpful questions to ask yourself

• Do I need all subarrays, or just contiguous ones?
• Can I maintain the current answer when the window moves?
• Is the window size fixed or variable?
• What makes a window valid or invalid?

Complexity analysis

Sliding window is valuable because it often reduces repeated work.

Complexity comparison

Why time is linear

Even though there is a nested while loop in some implementations, each element is added once and removed once. That means the total number of pointer moves is bounded by 2n, which is O(n).

Common pitfalls

1. Using sliding window when the problem is not contiguous

Sliding window only works for contiguous subarrays or substrings. It does not solve arbitrary subset problems.

2. Forgetting to update state when shrinking

If you use a frequency map, remember to decrement counts and remove keys when the count reaches zero.

3. Mixing up fixed and variable windows

For fixed-size windows, you know exactly when to remove the leftmost element. For variable-size windows, you shrink only when the condition breaks.

4. Off-by-one errors

Always check whether window length is right - left + 1.

Related patterns and problems

Sliding window often appears alongside these ideas:

• Two pointers: a broader pattern that includes sliding window
• Prefix sums: useful when you need fast range sum queries
• Monotonic deque: helpful for max/min in a window
• Hash map frequency counting: common in substring problems

Related interview problems

• Maximum sum subarray of size k
• Longest substring without repeating characters
• Minimum window substring
• Subarray sum equals k
• Find all anagrams in a string
• Longest repeating character replacement

Practice mindset: how to derive the solution quickly

When you see a new problem, try this process:

1. Identify whether the data is contiguous.
2. Decide whether the window size is fixed or variable.
3. Define the exact condition for validity.
4. Choose the state to maintain inside the window.
5. Ask how to update the state when the window expands or shrinks.

If you can answer those five questions, you can usually build the solution yourself instead of memorizing it.

Key takeaways

• Sliding window is a core interview pattern for contiguous array and string problems.
• It works by reusing previous work instead of recomputing from scratch.
• Fixed-size windows are great for problems like maximum sum subarray.
• Variable-size windows solve many substring problems with constraints.
• The pattern often gives O(n) time with simple code.

If you want to see the window move, the counts change, and the answer update step by step, I built an interactive version of this walkthrough at codebrew.ai — it may help if you learn best by tracing state visually.

Practice these next

Try these problems after this one:

1. Maximum Sum Subarray of Size K
2. Longest Substring Without Repeating Characters
3. Minimum Window Substring
4. Find All Anagrams in a String
5. Longest Repeating Character Replacement