AlgoScope

Substring Windows

algorithmintermediateTime O(n)Space O(alphabet)

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.

a0b1c2a3b4c5b6b7l

Longest substring of "abcabcbb" with no repeated character. The window [l, r] always holds distinct characters. r moves one step at a time; when s[r] is already inside, l jumps to just past the earlier copy, so each edge moves only forward and the scan is O(n).

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.

  1. Next character is 'a' and the window is "". What happens to l?

    • It stays at 0
    • It jumps to 1

    Answer: It stays at 0. No repeat, so nothing has to leave.

  2. Next character is 'b' and the window is "a". What happens to l?

    • It stays at 0
    • It jumps to 1

    Answer: It stays at 0. No repeat, so nothing has to leave.

  3. Next character is 'c' and the window is "ab". What happens to l?

    • It stays at 0
    • It jumps to 1

    Answer: It stays at 0. No repeat, so nothing has to leave.

  4. Next character is 'a' and the window is "abc". What happens to l?

    • It stays at 0
    • It jumps to 1

    Answer: It jumps to 1. The earlier 'a' at 0 must leave, and everything before it goes with it.

  5. Next character is 'b' and the window is "bca". What happens to l?

    • It stays at 1
    • It jumps to 2

    Answer: It jumps to 2. The earlier 'b' at 1 must leave, and everything before it goes with it.

  6. Next character is 'c' and the window is "cab". What happens to l?

    • It stays at 2
    • It jumps to 3

    Answer: It jumps to 3. The earlier 'c' at 2 must leave, and everything before it goes with it.

  7. Next character is 'b' and the window is "abc". What happens to l?

    • It stays at 3
    • It jumps to 5
    • It moves to 4

    Answer: It jumps to 5. The earlier 'b' at 4 must leave, and everything before it goes with it.

  8. Next character is 'b' and the window is "cb". What happens to l?

    • It stays at 5
    • It jumps to 7
    • It moves to 6

    Answer: It jumps to 7. The earlier 'b' at 6 must leave, and everything before it goes with it.

How it runs, step by step

  1. Longest substring of "abcabcbb" with no repeated character. The window [l, r] always holds distinct characters. r moves one step at a time; when s[r] is already inside, l jumps to just past the earlier copy, so each edge moves only forward and the scan is O(n).

    Longest substring without repeats over 8 characters.

  2. r = 0, 'a'. Not in the window, so it simply joins. Window "a" of length 1, a new best.

    Right 0 is a. Window from 0 to 0, length 1.

  3. r = 1, 'b'. Not in the window, so it simply joins. Window "ab" of length 2, a new best.

    Right 1 is b. Window from 0 to 1, length 2.

  4. r = 2, 'c'. Not in the window, so it simply joins. Window "abc" of length 3, a new best.

    Right 2 is c. Window from 0 to 2, length 3.

  5. r = 3, 'a'. 'a' is already inside at index 0, so l jumps from 0 to 1, just past that copy. Window "bca" of length 3.

    Right 3 is a. Window from 1 to 3, length 3.

  6. r = 4, 'b'. 'b' is already inside at index 1, so l jumps from 1 to 2, just past that copy. Window "cab" of length 3.

    Right 4 is b. Window from 2 to 4, length 3.

  7. r = 5, 'c'. 'c' is already inside at index 2, so l jumps from 2 to 3, just past that copy. Window "abc" of length 3.

    Right 5 is c. Window from 3 to 5, length 3.

  8. r = 6, 'b'. 'b' is already inside at index 4, so l jumps from 3 to 5, just past that copy. Window "cb" of length 2.

    Right 6 is b. Window from 5 to 6, length 2.

  9. r = 7, 'b'. 'b' is already inside at index 6, so l jumps from 5 to 7, just past that copy. Window "b" of length 1.

    Right 7 is b. Window from 7 to 7, length 1.

  10. Longest run without a repeat: "abc", length 3. Both edges only ever moved right, so the whole scan touched each character at most twice: O(n).

    Best length 3.

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;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

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.

Topics covered

Related

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

Next up