Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters is the classic introduction to the sliding window. It teaches a pattern that turns many "longest / shortest substring" problems from O(n²) into a clean single pass.

The slow way first

The obvious idea: try every starting point, and from each one extend as far as you can without a repeat. That is O(n²) — for a long string it is far too slow, and it redoes work the previous start already proved.

The better question: can I keep one window and slide it, instead of restarting? Yes. As the right edge moves forward, the only thing that can break the "no repeat" rule is the new character. If it causes a duplicate, we just shrink the left edge until the duplicate is gone.

The idea: a window that never repeats

Keep a window [L, R] and a set of the characters inside it. Move R forward one step at a time:

• If s[R] is not in the set, add it — the window grew, so update the best length.
• If s[R] is in the set, remove s[L] and move L right, again and again, until the duplicate is gone. Then add s[R].

Because each character enters the set once and leaves at most once, both pointers only ever move right. That is what makes it O(n).

The key insight: the window always holds a valid (no-repeat) substring, so its length at every step is a candidate answer.

Walk through it

Step through the animation. R scans left to right; the window set shows what is inside. When R hits a character that is already in the window ("a" at index 3, then "b", then "c"...), L jumps forward to drop the old copy. The best length locks in at 3 early and never grows.

Pseudocode

window = empty set        # characters currently inside [L, R]
best = 0
L = 0
for R from 0 to len(s) - 1:
    while s[R] is already in window:
        remove s[L] from window     # shrink from the left
        L = L + 1
    add s[R] to window
    best = max(best, R - L + 1)      # window length is a candidate
return best

The Python solution

def length_of_longest(s):
    window = set()
    best = 0
    L = 0
    for R in range(len(s)):
        while s[R] in window:
            window.remove(s[L])
            L += 1
        window.add(s[R])
        best = max(best, R - L + 1)
    return best

• window is a set of the characters in the current window, so s[R] in window is an O(1) check.
• L is the left edge; R (the loop variable) is the right edge.
• The while loop (lines 6–8) is the shrink: as long as the new character is already inside, we drop the leftmost character and move L right. This is what makes the window valid again.
• After shrinking, window.add(s[R]) brings the new character in.
• R - L + 1 is the current window length, and we keep the largest one in best.

Complexity

Both L and R move forward at most n times total, so the work is O(n). The extra space is O(k), where k is the number of distinct characters that can fit in the window (at most the alphabet size).

When this pattern shows up

Practice