LeetCode #3 Medium

Longest Substring Without Repeating Characters

Return the length of the longest substring of s with no repeating characters.

stringsliding-windowhash-table

02

Intuition

Keep a window that holds only distinct characters. As the right edge moves forward, if it hits a character already inside the window, jump the left edge just past that character's previous spot. The window never shrinks needlessly.

How to spot this pattern

Two clues put you on a sliding window: the answer is a contiguous stretch, and the constraint is monotone — once a window is invalid, growing it right can't fix it. Then ask whether the left edge should crawl or jump. If you can store where the offender was, jump the left edge past it in O(1) instead of shrinking one character at a time.

03

Approach

1

Checking every substring is quadratic

There are O(n²) substrings, and verifying each for distinct characters re-scans constantly. But the substrings overlap enormously — extending a known-good window by one character barely changes anything. That overlap is the cue for a sliding window: maintain one contiguous range and adjust its edges instead of rebuilding from scratch.

2

Grow the right edge, jump the left edge past repeats

Keep a window [left, right] that contains only distinct characters. Push right forward one character at a time. The only thing that can break the window is encountering a character already inside it — when that happens, we must move left just past that character's previous position so the duplicate falls out of the window. To know where that was, store each character's most recent index in a map.

3

Guard against stale positions; track the best

When s[right] was last seen at some index, only jump left if that index is ≥ left — otherwise the earlier occurrence is already outside the window and left must not move backward. After adjusting, record last[ch] = right and update best = max(best, right − left + 1). Each index enters and leaves the window once, so it's a single O(n) pass; space is bounded by the character set.

04

Solution & live demo

▶1class Solution:
▶2    def lengthOfLongestSubstring(self, s):
▶3        last = {}
▶4        left = 0
▶5        best = 0
▶6        for right, ch in enumerate(s):
▶7            if ch in last and last[ch] >= left:
▶8                left = last[ch] + 1
▶9            last[ch] = right
▶10            best = max(best, right - left + 1)
▶11        return best

05

Common pitfalls

Moving `left` backwards on a stale index

✗ Wrong

if ch in last:
    left = last[ch] + 1

✓ Right

if ch in last and last[ch] >= left:
    left = last[ch] + 1

last keeps every character ever seen, including ones already outside the window. On "abba", when the second a arrives left is already 2, but last['a'] is 0 — dragging left back to 1 re-admits the b that was deliberately excluded and reports 3. The >= left test ignores repeats that have already fallen out of the window.

Recording the character after measuring the window

✗ Wrong

best = max(best, right - left + 1)
last[ch] = right

✓ Right

last[ch] = right
best = max(best, right - left + 1)

Here it happens to be harmless, but it's fragile ordering: the window is only genuinely valid once the current character has been registered. Update state, then measure — the same discipline that keeps the crawling variant correct.

06

Edge cases

All identical characters, e.g. 'bbbb'

Each new character forces left to follow right, so the window length stays 1.

Empty string

The loop never runs; best stays 0.

Repeat that lies left of the window

The last[ch] >= left guard ignores stale occurrences, so left never moves backward.

07

Complexity

Time

O(n)

Space

O(min(n, charset))

Each index enters and leaves the window once; map holds at most one entry per distinct character.