TechPrep
Arrays and stringsReadLabPracticeCheck

Sliding window

Grow the right edge, shrink the left edge only when the window breaks its rule, and track the best window seen.

Longest Substring Without Repeating Characters. Return the length of the longest substring of s with no repeated character.

Signals that point here

The idea

Each index enters the window once (right edge) and leaves at most once (left edge), so the whole scan is linear even though the window size changes.

Here the window rule is "no repeats". Storing each character's last index lets the left edge jump directly past the repeat instead of stepping one at a time. The last[ch] >= left check matters: a repeat outside the window is not a repeat.

def longest_unique(s: str) -> int:
    last: dict[str, int] = {}       # char -> last index seen
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1     # jump past the earlier copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Complexity

O(n) time; O(min(n, alphabet)) space for the map.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: longest_unique("abba")

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Find the smallest subarray with sum at least S (all values positive).
  2. Longest substring with at most two distinct characters.
  3. Return the start index of every anagram of p inside s.

Check yourself

Why is a variable-size window still O(n)?

Each index is added once and removed at most once; the two edges together move at most 2n times.

When does the window pattern stop working?

When the condition is not monotone, e.g. sums with negative numbers.

Saved in this browser.