Longest Substring Without Repeating Characters

Expand every start

Pick each possible starting position and grow a set to the right. The first repeated character ends that attempt: every longer substring from the same start still contains the duplicate. An early cutoff also stops once the remaining suffix can't beat best.

def length_of_longest_substring(s: str) -> int:
    best = 0
 
    for start in range(len(s)):
        if len(s) - start <= best:
            break
 
        seen: set[str] = set()
        for end in range(start, len(s)):
            if s[end] in seen:
                break
            seen.add(s[end])
            best = max(best, end - start + 1)
 
    return best

Here Σ is the alphabet size — the number of different characters the input may use. Time O(n²), Space O(Σ) in the general case.

Last-seen window

A sliding window is a contiguous range whose edges move while you scan. Keep the window s[left:right + 1] duplicate-free. For each new character, its last saved index tells you whether it already lives inside that window.

If it does, jump left one position past that copy. Use max so an older copy outside the window never drags left backwards.

def length_of_longest_substring(s: str) -> int:
    last_seen: dict[str, int] = {}
    left = 0
    best = 0
 
    for right, char in enumerate(s):
        if char in last_seen:
            left = max(left, last_seen[char] + 1)
        last_seen[char] = right
        best = max(best, right - left + 1)
 
    return best

Each character enters the scan once, and left only moves forward. Time O(n), Space O(Σ) for the last-seen map. Printable ASCII fixes Σ at 95, but naming it keeps the reasoning useful for larger alphabets too.