Skip to content
{}

Lesson 28

Sliding Window

Reuse the work from the last window instead of recomputing the next one.

18 min

01Why it matters & the intuition

Any question about the best contiguous subarray or substring — longest, shortest, max sum, at most k distinct — is usually a sliding window. It is one of the highest-yield interview patterns.

Think of it like…

A train window: as the train moves one metre, one metre of view appears on the right and one disappears on the left. You don't re-look at the whole view — you just update for what entered and what left.

02See it move

Press play, then step through slowly. Change the input and predict the next frame before you click.

Sliding window · longest unique substring
interactive
1/17
0
a
L·R
1
b
2
c
3
a
4
b
5
c
6
b
7
b
8
x
9
y
10
z
›Window "a" has no repeats. Best so far: 1 ("a").
  • window
  • repeat
  • best

03Key ideas

Fixed-size window

Add the entering element, subtract the leaving element. Max sum of any k consecutive items becomes O(n).

Variable-size window

Expand right every step; shrink left while the window breaks the rule. Track the best valid window.

Window state

Keep what you need to test validity in O(1): a running sum, a character count map, or a set.

04Build it from scratch

A clean reference implementation. Read it line by line — then close it and write your own in the lab below.

typescript
function maxSumOfK(nums: number[], k: number): number {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let right = k; right < nums.length; right++) {
    sum += nums[right] - nums[right - k]; // slide
    best = Math.max(best, sum);
  }
  return best;
}

function longestUniqueSubstring(s: string): number {
  const lastSeen = new Map<string, number>();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const prev = lastSeen.get(s[right]);
    if (prev !== undefined && prev >= left) left = prev + 1; // shrink past the repeat
    lastSeen.set(s[right], right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

05Complexity

OperationTimeSpace
Fixed or variable windowO(n)O(k) for window state
Brute force over all subarraysO(n²) or worse—

06Check your understanding

Question 1

Q1.Max sum of 3 consecutive elements with a sliding window is…

Question 2

Q2.In a variable window you shrink from the left when…

Question 3

Q3.Which problem is NOT a natural sliding window?

07Code lab

Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.

Longest substring without repeats

Write length_of_longest_substring(s) returning the length of the longest substring with no repeated characters.

function: length_of_longest_substringPython starts when you get here
Two PointersBacktracking