Command Palette

Search for a command to run...

Hectal

Lesson 7.2 · Sliding Window

Variable Windows: Finding the Longest

Grow the right edge every step; when the window breaks the rule, shrink the left edge until it's valid again. Record the size after fixing.

15 min

Think of it like this

Stretching a measuring tape along a row of books looking for the longest run with no repeated colour. You pull the end forward one book at a time. When a colour repeats, you slide the start forward past the earlier book of that colour, then keep pulling.

1.Grow, then shrink

The right pointer moves every iteration and adds one element. If the window is now invalid (a repeated character, too many distinct values, a sum too large), a while loop moves the left pointer forward, removing elements, until it's valid. Then the window [left, right] is the longest valid window ending at right.

Each element is added once and removed at most once, so even with the inner while, total work is O(n).

▶ Dry run: Longest run without a repeated letters = "abcabcbb"
a
0
↑L
b
1
c
2
↑R
a
3
b
4
c
5
b
6
b
7

in window(list)

abc

best(vars)

3

Step 1/5Grow to "abc": all different. Length 3.

Remember

  • Right moves every step; left moves only to restore validity.
  • Measure the window after shrinking.
  • Total O(n): each element enters and leaves once.

Common mistakes

  • Using if instead of while to shrink (one step may not be enough).
  • Measuring before fixing the window.