Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example

Input: abcabcbb Output: 3 (the substring abc)

Approach

A variable-size sliding window with a set (or last-seen-index map) of characters currently in the window. Expand the right edge; whenever a repeat is found, shrink the left edge past the previous occurrence.

Walkthrough

python

1def longest_substring(s):
2    seen = {}
3    left = 0
4    best = 0
5    for right, ch in enumerate(s):
6        if ch in seen and seen[ch] >= left:
7            left = seen[ch] + 1
8        seen[ch] = right
9        best = max(best, right - left + 1)
10    return best

Step 1 / 6

right=0: 'a' hasn't been seen — window grows to length 1.

Walkthrough

python

1def longest_substring(s):
2    seen = {}
3    left = 0
4    best = 0
5    for right, ch in enumerate(s):
6        if ch in seen and seen[ch] >= left:
7            left = seen[ch] + 1
8        seen[ch] = right
9        best = max(best, right - left + 1)
10    return best

Step 1 / 6

right=0: 'a' hasn't been seen — window grows to length 1.