Substring Windows
A window over a string is two edges that only ever move right, and the trick in every variable-window problem is knowing what makes the left edge move. For the longest substring without repeats, a repeat arriving on the right forces the left edge past the earlier copy. For the smallest window that covers a set of characters, the left edge advances whenever the window is covered, shrinking it until the next step would break the coverage. Because neither edge ever steps back, every character is handled a constant number of times.
Smallest window of "adobecodebanc" containing every character of "abc" (with multiplicity). need counts what is still missing. Grow the window with r until nothing is missing, then shrink with l for as long as it stays covered, remembering the shortest window seen.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 13, with their answers.
'a' enters with 3 still missing. Missing becomes?
Answer: 2. A character the window still lacked arrived.
'd' enters with 2 still missing. Missing becomes?
Answer: 2. Only a character still lacking lowers missing.
'o' enters with 2 still missing. Missing becomes?
Answer: 2. Only a character still lacking lowers missing.
'b' enters with 2 still missing. Missing becomes?
Answer: 1. A character the window still lacked arrived.
'e' enters with 1 still missing. Missing becomes?
Answer: 1. Only a character still lacking lowers missing.
'c' enters with 1 still missing. Missing becomes?
Answer: 0. A character the window still lacked arrived.
'o' enters with 1 still missing. Missing becomes?
Answer: 1. Only a character still lacking lowers missing.
'd' enters with 1 still missing. Missing becomes?
Answer: 1. Only a character still lacking lowers missing.
'e' enters with 1 still missing. Missing becomes?
Answer: 1. Only a character still lacking lowers missing.
'b' enters with 1 still missing. Missing becomes?
Answer: 1. Only a character still lacking lowers missing.
'a' enters with 1 still missing. Missing becomes?
Answer: 0. A character the window still lacked arrived.
'n' enters with 1 still missing. Missing becomes?
Answer: 1. Only a character still lacking lowers missing.
'c' enters with 1 still missing. Missing becomes?
Answer: 0. A character the window still lacked arrived.
How it runs, step by step
Smallest window of "adobecodebanc" containing every character of "abc" (with multiplicity). need counts what is still missing. Grow the window with r until nothing is missing, then shrink with l for as long as it stays covered, remembering the shortest window seen.
Minimum window covering 3 characters.
r = 0, 'a' enters. It was still needed, so missing drops to 2.
Right 0 is a, missing 2.
r = 1, 'd' enters. Not a wanted character, so missing stays at 2.
Right 1 is d, missing 2.
r = 2, 'o' enters. Not a wanted character, so missing stays at 2.
Right 2 is o, missing 2.
r = 3, 'b' enters. It was still needed, so missing drops to 1.
Right 3 is b, missing 1.
r = 4, 'e' enters. Not a wanted character, so missing stays at 1.
Right 4 is e, missing 1.
r = 5, 'c' enters. It was still needed, so missing drops to 0. Everything is covered.
Right 5 is c, missing 0.
Window "adobec" of length 6 is the best so far. Shrink: 'a' leaves from the left. It was needed, so the window is no longer covered (missing 1) and r must move again.
Left moves to 1, missing 1.
r = 6, 'o' enters. Not a wanted character, so missing stays at 1.
Right 6 is o, missing 1.
r = 7, 'd' enters. Not a wanted character, so missing stays at 1.
Right 7 is d, missing 1.
r = 8, 'e' enters. Not a wanted character, so missing stays at 1.
Right 8 is e, missing 1.
r = 9, 'b' enters. The window already had enough of it, so missing stays at 1.
Right 9 is b, missing 1.
r = 10, 'a' enters. It was still needed, so missing drops to 0. Everything is covered.
Right 10 is a, missing 0.
Shrink: 'd' leaves from the left. It was surplus, so the window is still covered and can shrink further.
Left moves to 2, missing 0.
Shrink: 'o' leaves from the left. It was surplus, so the window is still covered and can shrink further.
Left moves to 3, missing 0.
Shrink: 'b' leaves from the left. It was surplus, so the window is still covered and can shrink further.
Left moves to 4, missing 0.
Shrink: 'e' leaves from the left. It was surplus, so the window is still covered and can shrink further.
Left moves to 5, missing 0.
Shrink: 'c' leaves from the left. It was needed, so the window is no longer covered (missing 1) and r must move again.
Left moves to 6, missing 1.
r = 11, 'n' enters. Not a wanted character, so missing stays at 1.
Right 11 is n, missing 1.
r = 12, 'c' enters. It was still needed, so missing drops to 0. Everything is covered.
Right 12 is c, missing 0.
Shrink: 'o' leaves from the left. It was surplus, so the window is still covered and can shrink further.
Left moves to 7, missing 0.
Shrink: 'd' leaves from the left. It was surplus, so the window is still covered and can shrink further.
Left moves to 8, missing 0.
Window "ebanc" of length 5 is the best so far. Shrink: 'e' leaves from the left. It was surplus, so the window is still covered and can shrink further.
Left moves to 9, missing 0.
Window "banc" of length 4 is the best so far. Shrink: 'b' leaves from the left. It was needed, so the window is no longer covered (missing 1) and r must move again.
Left moves to 10, missing 1.
Smallest covering window: "banc", length 4. Each edge moves only forward, so the scan is O(n) plus the alphabet for the counts.
Best window banc.
Write it yourself
Define longestWithoutRepeat(text) and return the length of the longest stretch with no character twice. It runs in your browser against this lesson's own 2 examples.
// Remember where each character was last seen, and jump the left edge past it rather than walking it forward.function longestWithoutRepeat(text) { return 0;}
Remember
- Both edges only move right, so a variable window costs O(n) even though the inner loop looks nested.
- No repeats: when s[r] is already inside, jump l to one past its earlier copy, not just one step.
- Min window: grow until missing is 0, then shrink while it stays 0, recording the shortest window.
Where this is used
DatabasesCover density ranking in PostgreSQL
ts_rank_cd scores a document by its covers, the shortest spans of text that contain all the query lexemes, so a document whose query words sit close together outranks one where they are scattered across a page. Finding a cover is this scan: extend the span until every term is present, then pull the left edge in while it stays present. That is why the function needs lexeme positions: it ignores stripped lexemes, and a tsvector with none left scores zero, because there is no window to measure.
Developer toolsMatch tightening in fzf
fzf's v1 matcher scans forward until the last character of the query has appeared in order, then scans backward from that point to find the shortest substring that still holds the whole query, and the score depends on how tight that substring came out. The backward pass is the shrink step, moving the left edge in as far as it can without losing a query character. The default v2 matcher pays more to score every occurrence, but v1 remains behind --algo=v1 because one forward and one backward pass per candidate is what keeps a million-line list answering each keystroke.
SearchMinimal intervals in Elasticsearch
The intervals query is defined on minimal intervals, spans of text containing the required terms with nothing trimmable off either end, and max_gaps rejects a span whose terms sit further apart than you allow. Keeping only the tightest span for each starting position is the same shrink, and Elasticsearch says plainly why it does this: minimizing every interval is what lets the query run in linear time. It also documents the price. Searching for salty contained_by the phrase hot porridge does not match the text "hot porridge is salty porridge", because the minimal hot porridge interval covers the first two terms and never reaches salty at all.
NetworkingThe IPsec anti-replay window
A receiver cannot remember every sequence number it has ever accepted, so it keeps a fixed window of recent ones. A number already inside the window is a replay and is dropped, a number to the left of it is too old to judge and is dropped as well, and a higher number drags the window forward and pushes the oldest number out. Both edges only move right, which is what lets the duplicate check be a bit test rather than a search.
Why it works this way
The stale index trap: why the test is seen >= left
lastSeen holds the index of every character the scan has ever met, including ones that fell off the left of the window long ago. Without the seen >= left guard an old copy drags left backwards and the window grows again. On "abba" the second a sits at index 3 while left is already 2, so left = lastSeen['a'] + 1 = 1 would re-admit both b's and report 3 instead of 2.
Why a surplus copy must not count towards coverage
missing is the number of required characters the window still owes, and it drops only when the arriving character is one that is still owed, which is what the need[c] > 0 test asks. Drop that test and spare copies count: with t = "AB" and s = "AA" the second A drives missing to 0, so the scan reports a cover although s holds no B at all. The counts are also allowed to fall below zero, and that surplus is exactly what the shrink step runs on, since putting a character back on the way out lifts its count above zero only when the window has no spare copy left.
Covering a set is not the same as containing a subsequence
The window covers the characters of t in any order, which is why "banc" covers "abc". If you need them in order the counting trick stops working, because a count reaching zero says nothing about position. The usual answer is a different pair of passes: scan forward until the last character of the pattern has matched in order, then scan backward to pull the start in as far as it will go.
A Char is not a character
The map is keyed by Kotlin's Char, which is one UTF-16 code unit, not one character. Two different emoji often share a high surrogate, since U+1F600 and U+1F601 are both D83D followed by different low surrogates, so a no-repeat scan sees a repeat that is not there and cuts the window short. On user-supplied text, step over code points or grapheme clusters and key the map on those; the window logic does not change, only the unit does.
Read more
- Two PointersUSACO Guide
- Distinct Values Subarrays II - counting windows with at most k distinct valuesCSES 2428 · cses.fi
- Controlling text search - ts_rank_cd and cover densityPostgreSQL manual · postgresql.org
- Intervals query and max_gapsElasticsearch reference · elastic.co
- fzf's matching algorithm, forward scan then backward scanfzf source · github.com
Next up
- Fixed-Size WindowA window of size k. Add what enters, subtract what leaves, never re-add the middle.
- Maximum Sum Subarray of Size kSlide a fixed window across the array and keep the best sum it ever held.
- Sliding WindowKeep a contiguous range and update its summary as it moves, instead of rescanning it.