Longest valid window

56 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

In the string abcabcbb, find the longest stretch with no repeated letter. By hand you would start at each position and extend to the right until a letter repeats: from 0 you get abc (then a repeats), from 1 you get bca, from 2 cab, and so on. The answer is 3.

That is a fresh scan from every start: n starts, each extending up to n, O(n²), and each extension needs a "have I seen this letter?" check. The waste is that the scan from position 1 re-reads bc, which the scan from position 0 already knew were distinct.

Build the structure, one piece at a time

Piece one: a window [l, r] with a set (or count table) of the letters inside it, so "is this letter already in the window?" is one step.

Piece two, the rule for the right end: always try to grow. Move r one step right and add the new letter to the set.

Piece three, the rule for the left end: if the window just became invalid (the new letter was already inside), shrink from the left, removing letters from the set, until the window is valid again. Then record the window's length if it is the longest so far.

The word "valid" is the only thing that changes between problems: "no repeated letter", "at most k distinct values", "at most k zeros flipped", "the most frequent letter can be made to fill the window with at most k replacements". The aggregate is whatever lets you test validity in O(1) after each add or remove.

Why it is correct

The invariant, true after every shrink loop: [l, r] is valid, and no window ending at r that starts before l is valid. The first half is just what the shrink loop guarantees. For the second half, suppose some window [l′, r] with l′ < l were valid. The shrink loop only advances l while the window is invalid, so at the moment l moved past l′ the window [l′, r″] was invalid for some r″ ≤ r. Validity here is hereditary: a window with a repeat still has that repeat when you extend it. So [l′, r] is invalid too. Hence for each r the window [l, r] is the longest valid window ending at r, and the maximum over all r is the longest valid window overall. The argument needs that property: if a window is invalid, every larger window containing it is invalid. Every "at most k" constraint has it.

Why it is fast

Count pointer moves. r moves right exactly n times. l only ever moves right, and it never passes r, so it moves at most n times in total across all shrink loops, even though one loop may move it several steps:

total moves ≤ n (for r) + n (for l) = 2n

Each move does O(1) work on the set. So the time is O(n), with O(alphabet) memory. The quadratic rescans are gone because the left end never goes backwards.

How to recognise it in an interview

Cues: "longest substring/subarray such that …", with a condition of the form "at most", "no", "without". The answer is a length and the condition is hereditary. The first thing to say: "I will grow the right end every step and shrink the left end only while the window is invalid; each pointer moves at most n times."

Longest Substring Without Repeating Characters is the example. Fruit Into Baskets is "at most 2 distinct values" with a count table. Longest Repeating Character Replacement is valid while window length − (count of the most frequent letter) ≤ k; the standard trick keeps the historical maximum count, which never makes the answer wrong because the best window only needs to be found once.

02The idea in one line

Grow right; while invalid, shrink left; record the longest valid span.

Reach for it when: Longest substring with ≤k distinct / no repeats / ≤k replacements.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Longest Substring Without Repeating Characters on 'abcabcbb'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Grow r; while the window has a repeat, shrink l; record the longest valid span
2. Window [0..0] = 'a' is valid, length 1, best = 1
3. Window [0..1] = 'ab' is valid, length 2, best = 2
4. Window [0..2] = 'abc' is valid, length 3, best = 3
5. 'a' repeats at index 0: jump l to 1
6. Window [1..3] = 'bca' is valid, length 3, best = 3
7. 'b' repeats at index 1: jump l to 2
8. Window [2..4] = 'cab' is valid, length 3, best = 3
9. 'c' repeats at index 2: jump l to 3
10. Window [3..5] = 'abc' is valid, length 3, best = 3
11. 'b' repeats at index 4: jump l to 5
12. Window [5..6] = 'cb' is valid, length 2
13. 'b' repeats at index 6: jump l to 7
14. Window [7..7] = 'b' is valid, length 1
15. Longest: 'abc' → 3
16. l and r only move right: O(n) with a last-seen map

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Sliding Window: Fixed-size window, Shortest satisfying window, Count windows via at-most(k) trick, Window with a need-counter.