Longest Substring Without Repeating Characters Solution

Problem

Given a string, find the length of the longest contiguous block of characters where every character appears exactly once. You need to find the length, not the substring itself.

Input: s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest run without any character appearing twice

A tricky case: "bbbbb" returns 1 because every extension immediately creates a repeat.

Intuition

The problem asks how far right you can stretch a window before a character appears twice. Instead of restarting from scratch when you hit a duplicate, you can slide the left boundary past the earlier copy — the characters between are still all unique and can anchor the next stretch. Remembering where you last saw each character (not just whether you saw it) lets you jump the left boundary in one step rather than walking it forward character by character.

Approach 1 — Brute Force

For each starting position, expand right using a set until a duplicate is found. The maximum window seen across all starting positions is the answer.

For each index start from 0 to end, initialize an empty set and end = start.
While end < len(s) and s[end] is not in the set, add s[end] to the set and increment end.
Record max_length = max(max_length, end - start).
Return max_length.

1def length_of_longest_substring(s: str) -> int:
2    max_length = 0
3    for start in range(len(s)):
4        seen = set()
5        end = start
6        while end < len(s) and s[end] not in seen:
7            seen.add(s[end])
8            end += 1
9        max_length = max(max_length, end - start)
10    return max_length

Time: O(n²) — in the worst case (all identical characters) the outer loop runs n times and the inner loop processes one character each time, but averaged across distinct characters the inner loop does O(n) total work per outer step.

Space: O(min(n, m)) — the set holds at most the number of distinct characters in the alphabet m, or n if n is smaller.

Approach 2 — Sliding Window with Hash Map

Maintain a window [left, right]. Store each character's most recent index. When a duplicate is found, jump left directly past the previous occurrence — skipping the slow one-by-one shrink.

Initialize last_seen map, left = 0, max_length = 0.
For each right, look up whether the current character is in last_seen with index >= left (inside the current window).
If so, jump left = last_seen[char] + 1 to exclude the earlier copy.
Update last_seen[char] = right.
Update max_length = max(max_length, right - left + 1).
Return max_length.

1def length_of_longest_substring(s: str) -> int:
2    last_seen = {}  # char -> index of most recent occurrence
3    left = 0
4    max_length = 0
5
6    for right, char in enumerate(s):
7        if char in last_seen and last_seen[char] >= left:
8            # jump past the earlier copy; the >= left guard prevents
9            # moving left backwards when a stale entry is outside the window
10            left = last_seen[char] + 1
11        last_seen[char] = right
12        max_length = max(max_length, right - left + 1)
13
14    return max_length

Time: O(n) — each character is visited exactly once by the right pointer; left only moves forward, never back.

Space: O(min(n, m)) — the map holds at most one entry per distinct character, bounded by the alphabet size m.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(min(n, m))	Understanding the problem; tiny inputs where clarity beats speed
Sliding Window with Hash Map	O(n)	O(min(n, m))	Always prefer this — same space, linear time

Common Mistakes

Forgetting the >= left guard on the map lookup — last_seen is never cleared, so a character encountered before the current window still has an old entry; without the guard, left jumps backwards into territory already confirmed unique.
Using left = last_seen[char] instead of last_seen[char] + 1 — this keeps the duplicate character inside the window, making the window invalid immediately.
Computing window size as right - left instead of right - left + 1 — the window is inclusive on both ends; skipping +1 consistently under-counts by one.
Returning the final window size instead of max_length — the largest window is not necessarily the last one; you must track the running maximum.
Using a set and shrinking left one step at a time — correct but O(n) per shrink in the worst case without the jump trick; the hash map avoids this while using the same space.

Longest Substring Without Repeating Characters — Solution