Longest Substring Without Repeating Characters

The problem

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

Function: def lengthOfLongestSubstring(s):

Example input (a JSON list of arguments): ["abcabcbb"]
Expected output: 3

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Maintain a window with unique characters and remember each character's latest index.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def lengthOfLongestSubstring(s):
    seen={}; left=best=0
    for right,c in enumerate(s):
        left=max(left,seen.get(c,-1)+1); seen[c]=right; best=max(best,right-left+1)
    return best

Why it works

Maintain a window with unique characters and remember each character's latest index. Advance the left bound past a repeated character only when that occurrence is still inside the window.

Complexity: O(n) time / O(min(n,alphabet)) space.

Time: O(n) time · Space: O(min(n,alphabet)) space