📊 We use cookies & analytics to improve your experience. Learn more
Latest

Interview DSA Crash Course Module 2 · Lesson 7 of 15

0% Exit to course

Module 2 · Arrays, strings and hashing Lesson 7 of 15

Sliding window

Learning objective

A moving window over a sequence is the standard answer to "longest/shortest subarray with some property" — including at non-coding companies that ask only this.

The concept

A sliding window is a range that grows on the right and shrinks on the left while you keep a running answer. "Longest substring without repeating characters" and "smallest subarray with sum at least k" are the same technique: extend until a rule breaks, then move the left edge in until it holds again.

The window needs a small piece of state — a set of characters, a sum, a count map — and the loop looks the same each time: add the new item, fix the violation by moving left, update the best answer. Written that way it is O(n) with two pointers that never move backwards.

Python
def longest_unique(s):
    seen, left, best = set(), 0, 0
    for right, ch in enumerate(s):
        while ch in seen:              # shrink until the rule holds again
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

# O(n): each index is added and removed at most once.

Common mistakes

The mistakes are updating the best answer after shrinking instead of before, and forgetting to remove the item you left behind when the window moves — which produces an answer that is too long and looks almost right in a test. Trace one small example by hand before you run it.

Worked example

Longest substring without repeating characters: grow the window on the right, shrink from the left while a duplicate exists, remember the largest size. One pass, O(n).

Your practice task

Implement the longest-substring window and a fixed-size maximum-sum window, and compare both against a brute-force version.

Do this before moving on. Reading a solution teaches the shape of it; typing it teaches you.

Key takeaway

A sliding window is a range that grows on the right and shrinks on the left while you keep a running answer.

Create free account or sign in

Almost there

15 lessons left of 15

Finish every lesson to unlock the certificate. Each one ends in a practice task — do them and the final project brief writes itself.