Longest Substring Without Repeats

Medium · rating 1500 · Sliding Window, Hashing, Strings

Read a string of lowercase letters. Print the length of the longest substring that contains no repeated character.

For abcabcbb the answer is 3 (abc).

Constraints: 1 ≤ length ≤ 105

Editorial

Approach

Slide a window over the string, remembering the last index each character was seen. When the current character was already inside the window, jump the left edge just past its previous position. The answer is the largest window width seen.

Why the jump is correct

Shrinking straight to after the duplicate restores the no-repeat invariant in one move, so the window's left edge only ever moves forward — a single linear pass.

seen = {}
i = best = 0
for j, ch in enumerate(s):
    if ch in seen and seen[ch] >= i:
        i = seen[ch] + 1
    seen[ch] = j
    best = max(best, j - i + 1)

Complexity

Time: O(n). Space: O(k) for the alphabet.

Related problems

Open Longest Substring Without Repeats in Code Arena →