3. Longest Substring Without Repeating Characters

MediumSliding WindowTwo pointers + hash mapVariable-size sliding window with last-seen index

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring (contiguous run of characters) that contains no repeated character.

Open official problem prompt ↗

In plain English

Measure the longest contiguous piece of the string in which every character is unique.

Picture it like this

Reading a hallway of numbered doors and keeping the longest stretch you can walk without passing the same door number twice; the moment you'd repeat one, you restart just past its first occurrence.

Example

Input: s = "abcabcbb"
Output: 3
Why: The longest substring with all distinct characters is "abc", which has length 3.

Constraints

0 <= s.length <= 5 * 10^4s consists of English letters, digits, symbols and spaces

Pattern lesson

See the pattern, then code

Variable-size sliding window with last-seen index

↗

Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. Grow a window to the right; when the incoming character duplicates one already inside the window, jump the left edge to just past that character's previous position so the window is valid again.

New words, made simpleKnow these before the algorithm

Window: The contiguous substring currently under consideration, bounded by start and right.
Last-seen map: A hash map from each character to the most recent index at which it appeared.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force over all substrings

Recomputes uniqueness from scratch for every substring; far too slow.

Check every start/end pair and test each substring for uniqueness with a set.

Time O(n^3)Space O(min(n,k))

Best choiceSliding window with last-seen index

Each index is visited once and the left edge only moves forward, giving linear time.

Expand right, and on a repeat jump the left edge past the previous occurrence in O(1).

Time O(n)Space O(min(n,k))

The rule we keep true

Invariant

The substring from start to right always contains no repeated character.

Why this is correct

Reasoning

When a duplicate arrives, any valid window ending at the current index must start after the previous occurrence of that character. Moving start to last+1 restores uniqueness without discarding any window that could be longer, and since start never moves backward, every character is processed a constant number of times.

The algorithm in three movesSay these aloud before coding

1Track the last index where each character was seen

start=0, i=2 -> window 'abc' len 3

2For each right index, if the char was seen at or after the current start, move start to last+1

i=3 'a' seen at 0 -> start=1

3Update the last-seen index of the current char

best stays 3

4Record the best window length (right - start + 1)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readindices 0,1,2

2 · AskAny duplicate inside the window?

3 · Update statelast={a:0,b:1,c:2}, start=0

4 · ResultWindow 'abc', best = 3

Key takeaway

The window a,b,c (indices 0-2) is the longest run before a repeat forces the left edge forward.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Initialize state
last maps characters to their most recent index; start is the window's left edge; best is the answer so far.
2
Lines 7-8Handle a repeat
If the current char was seen at an index still inside the window, advance start past it so the window is valid again.
3
Lines 9-10Record and measure
Update the char's last index, then update best with the current window width.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty string returns 0
All identical characters like 'bbbb' returns 1
All distinct characters returns the full length
Single character returns 1

Common beginner mistakes

Forgetting the 'last[ch] >= start' guard and jumping start backward on a stale occurrence
Resetting start all the way to the duplicate's index instead of one past it
Using a set and shrinking one step at a time (still O(n) but easy to get wrong) versus the O(1) index jump

Check your understanding

Why must we check that the previous occurrence index is >= start before moving the left edge?

Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Sliding Window