AlgoScope

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.

The player

Longest substring without repeats over 8 characters.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.

The code

Substring Windows, in Python

def longest_without_repeat(s):
    last_seen = {}
    left = 0; best = 0
    for right in range(len(s)):
        seen = last_seen.get(s[right])
        if seen is not None and seen >= left: left = seen + 1    # repeat inside: jump past the copy
        last_seen[s[right]] = right
        best = max(best, right - left + 1)
    return best

def min_window(s, t):
    need = {}
    for ch in t: need[ch] = need.get(ch, 0) + 1                  # counts still missing
    missing = len(t); left = 0; best = ""
    for right in range(len(s)):
        if need.get(s[right], 0) > 0: missing -= 1               # a wanted character enters
        need[s[right]] = need.get(s[right], 0) - 1
        while missing == 0:                                      # covered: shrink while it stays covered
            if not best or right - left + 1 < len(best): best = s[left:right + 1]
            need[s[left]] = need.get(s[left], 0) + 1
            if need[s[left]] > 0: missing += 1                   # a wanted character leaves
            left += 1
    return best

Substring Windows, in JavaScript

function longestWithoutRepeat(s) {
  const lastSeen = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const seen = lastSeen.get(s[right]);
    if (seen !== undefined && seen >= left) left = seen + 1;   // repeat inside: jump past the copy
    lastSeen.set(s[right], right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

function minWindow(s, t) {
  const need = new Map();                                      // counts still missing
  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
  let missing = t.length;
  let left = 0;
  let best = "";
  for (let right = 0; right < s.length; right++) {
    if ((need.get(s[right]) ?? 0) > 0) missing--;              // a wanted character enters
    need.set(s[right], (need.get(s[right]) ?? 0) - 1);
    while (missing === 0) {                                    // covered: shrink while it stays covered
      if (!best || right - left + 1 < best.length) best = s.slice(left, right + 1);
      need.set(s[left], (need.get(s[left]) ?? 0) + 1);
      if (need.get(s[left]) > 0) missing++;                    // a wanted character leaves
      left++;
    }
  }
  return best;
}

Substring Windows, in Kotlin

fun longestWithoutRepeat(s: String): Int {
    val lastSeen = mutableMapOf<Char, Int>()
    var left = 0; var best = 0
    for (right in s.indices) {
        val seen = lastSeen[s[right]]
        if (seen != null && seen >= left) left = seen + 1     // repeat inside: jump past the copy
        lastSeen[s[right]] = right
        best = maxOf(best, right - left + 1)
    }
    return best
}

fun minWindow(s: String, t: String): String {
    val need = t.groupingBy { it }.eachCount().toMutableMap()   // counts still missing
    var missing = t.length; var left = 0; var best = ""
    for (right in s.indices) {
        if ((need[s[right]] ?: 0) > 0) missing--                // a wanted character enters
        need.merge(s[right], -1, Int::plus)
        while (missing == 0) {                                  // covered: shrink while it stays covered
            if (best.isEmpty() || right - left + 1 < best.length) best = s.substring(left, right + 1)
            need.merge(s[left], 1, Int::plus)
            if (need[s[left]]!! > 0) missing++                  // a wanted character leaves
            left++
        }
    }
    return best
}

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;}
6 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.

    Where this is used

    Cover density ranking in PostgreSQLDatabases

    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.

    Match tightening in fzfDeveloper tools

    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.

    Minimal intervals in ElasticsearchSearch

    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.

    The IPsec anti-replay windowNetworking

    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

    Sliding Window Maximum

    Maximum of every 3

    Next lesson: Sliding Window Maximum