Longest Substring Without Repeating Characters

mediumTests passed 2026-11-11v1.0.0

TC: O(N)|SC: O(min(N, Sigma))

Sliding Window Original Statement (leetcode).md

1. Core Invariant / The Trick

Store `{ char: lastIndex }`. When character `c` repeats at `r` and `lastIndex[c] >= l`, jump left pointer directly to `lastIndex[c] + 1` in O(1) instead of creeping `l` step-by-step.

2. Complexity Bounds & Proof

Right pointer visits N positions; left jumps monotonically forward.

3. Minimal Idiomatic Code

def lengthOfLongestSubstring(s: str) -> int:
    seen = {}
    l = best = 0
    for r, c in enumerate(s):
        if c in seen and seen[c] >= l:
            l = seen[c] + 1
        seen[c] = r
        best = max(best, r - l + 1)
    return best

4. Failure Modes & Interview Follow-ups

Pitfalls:- Only update `l = max(l, lastSeen[c] + 1)` so `l` never walks backward when meeting stale map entries.

Follow-ups:- At most K distinct chars: shrink left whenever `map.size > k`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Minimum Window Substring (O(|S| + |T|))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.