Lesson 10 · Core patterns

Sliding window — longest/shortest contiguous run

📖 Walk me through it — plain English

The job: given a string of characters, find the length of the longest stretch of back-to-back characters that has no repeats. "Back-to-back" (the word "contiguous") means the characters must sit next to each other — no skipping around. For "abcabcbb" the answer is 3, because "abc" is the longest run where every letter is different.

A "sliding window" is just a pair of markers — a left edge and a right edge — that fences off the slice of the string we are currently looking at. The plan: keep pushing the right edge forward one character at a time to grow the window. The moment that newest character creates a duplicate inside the fence, we yank the left edge forward just far enough to drop the older copy, so the window holds only distinct characters again. After every move we record the window's length if it beats our best so far.

The clever part is knowing how far to jump left. We keep a little notebook called last that remembers, for each character, the index where we most recently saw it. When the new character ch is one we have seen before and that earlier sighting is still inside our fence (last[ch] >= left), we slide left to one past that old position — instantly skipping the duplicate without checking every cell in between.

Analogy: you are reading a row of name tags, gathering the longest run of all-different names. You hold a sticky note at the start of your current run. When you hit a name you already have, you don't back up one step at a time — you remember exactly where that name first appeared and jump your sticky note to right after it. Everything from there to now is fresh again.

String "abcabcbb". Step 1 · right lands on 'a' (index 0). Never seen it, so the window is just this one cell. best = 1. (Accent marks the current window; cells past it haven't been reached yet.)

Step 2 · right moves to 'b' (index 1). Still no repeat, so left stays put and the window grows to "ab". Length = right − left + 1 = 1 − 0 + 1 = 2. best = 2.

Step 3 · right moves to 'c' (index 2). Still all distinct, window is "abc". Length = 2 − 0 + 1 = 3. best = 3. This is the winner, though we don't know that yet.

Step 4 · right moves to 'a' (index 3). Our notebook says 'a' last appeared at index 0, and 0 >= left(0), so that copy is inside the fence — a real repeat. Jump left to 0 + 1 = 1, dropping the old 'a' (now greyed and struck out). Window becomes "bca". Length = 3 − 1 + 1 = 3. best stays 3.

…the same dance continues for indices 4–7 (each new letter is a repeat inside the window, so left keeps nudging forward and no window ever beats 3). When right runs off the end, best is the answer: 3 — the run "abc" highlighted below.

Why it's fast: the right edge visits each character once, and the left edge only ever moves forward — it never backtracks. So across the whole run each marker travels the length of the string at most once. That's O(n) time (work grows in a straight line with the string length n), and the last notebook holds at most one entry per distinct character, so O(k) extra memory where k is the alphabet size. The reason it's correct: by jumping left to one past any duplicate, we guarantee the window between the two markers is always free of repeats, so every length we measure is a valid candidate — and we keep the biggest one.

Expand right; shrink left while the invariant is broken. Update answer at the right moment.

Trigger signals

"Longest substring with property"
"Smallest subarray with sum ≥ k"
"At most K of something"
Fixed window of size k

Gotchas

Shrink while invariant broken, not if
Update answer after restore, not during break
Window length = j - i + 1
Initialize counts before the loop

Template — Longest Substring Without Repeating

def length_of_longest(s):
    last = {}; left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

function lengthOfLongest(s: string): number {
  const last = new Map<string,number>();
  let left=0, best=0;
  for (let right=0; right<s.length; right++) {
    const ch = s[right];
    if (last.has(ch) && last.get(ch)! >= left) left = last.get(ch)! + 1;
    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Write the fixed-size window yourself — add the entering element, drop the leaving one, never re-sum. Live tests below:

SoloMock: Longest Substring Without Repeating · Best Time Buy/Sell Stock

→ Going deeper: Sliding windows often use two pointers (left and right). See Two pointers.

→ Going deeper: When the window is fixed-size sums, prefix sums answer range queries in O(1). See Prefix sums.