# Longest Substring Without Repeating Characters

- **Canonical ID**: `longest-substring-without-repeating-characters`
- **Canonical URL**: https://dsacheatsheet.com/problems/longest-substring-without-repeating-characters
- **Difficulty**: medium
- **Patterns**: Sliding Window
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/longest-substring-without-repeating-characters/

## 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

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(min(N, Sigma))`
- **Proof**: Right pointer visits N positions; left jumps monotonically forward.

## 3. Minimal Idiomatic Code

### Python
```python
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
```

### TypeScript
```typescript
export function lengthOfLongestSubstring(s: string): number {
  const seen = new Map<string, number>();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    const prev = seen.get(c);
    if (prev !== undefined && prev >= l) l = prev + 1;
    seen.set(c, r);
    if (r - l + 1 > best) best = r - l + 1;
  }
  return best;
}
```

### C++
```cpp
int lengthOfLongestSubstring(string s) {
    int pos[128]; fill(begin(pos), end(pos), -1);
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); ++r) {
        l = max(l, pos[(unsigned char)s[r]] + 1);
        pos[(unsigned char)s[r]] = r;
        best = max(best, r - l + 1);
    }
    return best;
}
```

### Java
```java
int lengthOfLongestSubstring(String s) {
    int[] pos = new int[128]; Arrays.fill(pos, -1);
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        l = Math.max(l, pos[s.charAt(r)] + 1);
        pos[s.charAt(r)] = r;
        best = Math.max(best, r - l + 1);
    }
    return best;
}
```

### Go
```go
func lengthOfLongestSubstring(s string) int {
    var seen [128]int
    for i := range seen { seen[i] = -1 }
    l, best := 0, 0
    for r := 0; r < len(s); r++ {
        if seen[s[r]] >= l { l = seen[s[r]] + 1 }
        seen[s[r]] = r
        if r-l+1 > best { 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`.