Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring that contains no repeating characters.

A substring is a contiguous run of characters within the string.

Hints

· Stuck? Reveal one nudge at a time.

Keep a window of characters with no repeats; how do you react when a repeat enters?

Extend the right edge each step; on a duplicate, move the left edge forward.

Shrink from the left only until the repeated character is removed, then record the length.

Common doubts

The left pointer only moves forward and never past the right pointer, so across the whole run it advances at most n times total — the inner loop is amortized O(1).

Keep shrinking until the specific repeated character leaves the window — usually a few steps, exactly enough to restore uniqueness.

Yes — storing each character's last index lets you jump left directly past the previous occurrence, a common O(n) variant.

Interview follow-ups

· What an interviewer asks next.

Track the (left, right) pair whenever you update the best length, then slice the string at the end.

Swap the validity check: keep counts and shrink while any character's count exceeds the allowed repeats — the same template with a different invalid condition.

Fun facts

This is the archetypal variable-size sliding window — nearly every 'longest substring with property X' problem is this template with a different validity test.
The last-seen-index variant is a favorite because it turns the inner while-loop into a single pointer jump.

Asked at

AmazonGoogleMicrosoftMetaBloomberg

Frequently Sometimes Occasionally

Example 1

Input: s = "abcabcbb"
Output: 3
The longest substring without repeats is "abc", of length 3.

Example 2

Input: s = "bbbbb"
Output: 1
The best is "b", of length 1.

Constraints

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

A window s[left..right] is "valid" when it has no repeated character. Grow it by moving right; the moment the new character is already inside, slide left forward until the duplicate is gone. Every character enters and leaves the window at most once, so a single pass finds the longest valid window.

Prerequisites

Before you start

· Concepts used directly in the solution.

Two-pointer window. A window defined by a moving left and right index over the string.

Set / hash membership. Constant-time checks for "is this character currently in the window?".

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definitions

“Substring or subsequence?”

Substring — the characters must be contiguous.

“What counts as a repeat?”

Any character appearing more than once inside the current window makes it invalid.

Edges

“What about an empty string?”

The answer is 0 — there's no character to include.

The ideal opening — say it like this

I'll keep a window with no repeated characters, tracked in a set.

I extend the right edge each step; if the new character is already in the window, I shrink from the left until it isn't.

After each step the window is valid, so I record its length as a candidate answer.

Understand the problem

Worked example — s = "abcabcbb"

right=0 a  window "a"    best 1
right=1 b  window "ab"   best 2
right=2 c  window "abc"  best 3
right=3 a  dup! shrink -> window "bca" best 3
right=4 b  dup! shrink -> window "cab" best 3
...
answer: 3

Key observations

1Aha

Only shrink when a duplicate appears

The window stays valid as long as new characters are fresh. You contract from the left exactly when the incoming character collides with one already inside.

2Aha

Shrinking removes the old copy

Advancing left and deleting from the set is guaranteed to eventually remove the earlier occurrence of s[right], restoring uniqueness.

3Aha

Each character enters and leaves once

right and left both move only forward across the string, so despite the inner loop the total work is O(n).

Brute force vs optimal

	Extend from each start	Sliding window
Idea	From each index, extend while unique	One window, shrink only on a duplicate
Time	O(n^2)	O(n)
Space	O(min(n, alphabet))	O(min(n, alphabet))

The brute restarts the scan from every index; the window reuses the previous work by only ever moving both pointers forward. Full code is in the Approaches selector below.

Summary

Key takeaway

Keep a window with no repeats using a set. Extend right; whenever s[right] is already inside, advance left (removing characters) until it isn't, then record right - left + 1. Both pointers move forward only, so it's a single O(n) pass.

seen = set(); left = 0; best = 0
for right in 0 .. n-1:
    while s[right] in seen: remove s[left]; left += 1
    add s[right]; best = max(best, right - left + 1)
return best