Variable-Size Sliding Window

Foundations

In the first lesson, a fixed window of k elements slid one step at a time. Now, what if the window's length is the answer itself, so its two edges must move separately as the elements inside it change?

A variable window keeps a rule true for everything inside it. Each step, right takes in the next element; if that breaks the rule, left moves forward until it holds again. Nothing restarts: a window that obeys the rule still obeys it after losing elements from the left, so the elements kept need no second check. The answer is the largest right - left + 1 seen while the rule holds.

On nums = [7, 1, 5, 3, 6], find the longest window whose sum is at most 10. Taking in 7 and 1 gives sum 8. Taking in 5 makes 13, so left drops 7, leaving [1, 5]; 3 then fits, for [1, 5, 3] and length 3. Taking in 6 makes 15, so left drops 1 and 5, leaving [3, 6]. The longest window was 3, found in one pass with each element entering once.

• Hash Map Complement Lookup

  The walkthrough keeps a dict from each element to the index where it last appeared, the way Two Sum stored seen[x] = i.

  Open lesson

Case Scenario

Longest Substring Without Repeating Characters is a variable window over a string, indexed from 0: the rule is that no character appears twice between left and right. When s[right] repeats a character inside the window, left jumps one past that character's last index, which a hash map from character to index answers in O(1). In s = "tmmzuxt", the longest such window is "mzuxt", length 5.

The direct approach restarts at every index: from each i, it extends a run one character at a time, using a set to spot the first repeat. Up to n starts with up to n steps each is O(n²), and every restart forgets what the one before it proved. Step through the restarts below to see how much each one re-reads.