Longest substring without repeats

Lesson 1.3 · Medium · Variable window · 10 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

Given a string, find the length of the longest substring with no repeated letter.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

L/Ra0

z10

w11

v12

u13

a14

q15

r16

s17

t18

Take "a" in. Length is 1.

window "a" · best 1

1 / 27

The idea

Complexity

Time	Space	Why
`O(n)`	`O(min(n, alphabet))`	L and R each move at most n times; the map holds the letters in the window.

In Python

def longest_unique(s):
    seen, l, best = set(), 0, 0
    for r, ch in enumerate(s):
        while ch in seen:          # shrink until valid again
            seen.remove(s[l]); l += 1
        seen.add(ch)
        best = max(best, r - l + 1)
    return best

</> Now code it →Try it on LeetCode: Longest Substring Without Repeating Characters →

Summary: say it in the interview

Grow R one letter at a time. If the new letter is already inside, shrink L until it is gone. Track the best length after each step.
Time O(n), space O(min(n, alphabet)). L and R each move at most n times; the map holds the letters in the window.