Sliding Window

Opening scenario

Longest Substring Without Repeating Characters (LC 3). Given a string s, return the length of the longest substring with no repeated characters. s = "abcabcbb" → 3 ("abc"). Follow-up you should expect: Minimum Window Substring (LC 76) — the smallest substring of s that contains every character of t (with multiplicity).

LC numbers identify LeetCode problems.

A substring is contiguous. In LC 76, “with multiplicity” means that t = "AAB" requires at least two As and one B; return "" if no window qualifies. The template also returns "" for empty s or t. As the right boundary advances, which information can you update instead of recomputing it?

Question progression

Q1 — What is the brute force, and what is it recomputing?

Question: How do you find the longest no-repeat substring naively, and what is the cost?

Reasoning: Enumerate every start i, extend j until you hit a repeat — O(n^2) substrings, and…