Longest Substring Without Repeating Characters
Problem Statement
Given a string s, return the length of the longest substring that contains no repeated characters. A substring must be contiguous, so you may only move a window over adjacent characters.
Input
A string s.
Output
An integer: the maximum length of a contiguous substring with all unique characters.
Constraints
- •
0 <= s.length <= 5 * 10^4 - •
s consists of English letters, digits, symbols, and spaces
Examples
Example 1
s = abcabcbb
3Example 2
s = bbbbb
1Example 3
s = pwwkew
3Learning Objectives
- Identify a longest-valid variable window where the condition is all characters are unique.
- Maintain the left boundary so every window considered after shrinking is duplicate-free.
- Use last-seen indices to jump left directly past the previous duplicate.
- Explain why each character enters and leaves the window at most once.
Intuition
Pattern Identification
This is a longest-valid variable-window problem: among all contiguous substrings, we want the largest one that satisfies a local condition. The condition is monotone with respect to shrinking: if a window has a duplicate, moving left rightward can only remove characters and eventually restore uniqueness.
The expand and shrink invariant is: after processing each right index, the active window s[left...right] contains no repeated characters. When a duplicate enters, do not restart the search. Move left just beyond the previous occurrence if that occurrence is still inside the current window, then keep expanding from there.
Common mistakes
- ×Resetting the whole window to **right + 1** after a duplicate, which discards valid characters after the previous duplicate.
- ×Moving **left** backward when the last seen duplicate is outside the current window.
- ×Using a set but removing only one character when the duplicate may require multiple removals.
- ×Returning the substring itself when the problem asks for only its length.
Algorithm Explanation
Window setup
Keep two boundaries, left and right, representing the current substring. Store the most recent index of each character. The invariant is that every character inside left...right appears once.
Window visualization
For s = abcabcbb, the window grows through abc with left = 0 and right = 2, so the best length becomes 3. When right reaches the second a at index 3, the previous a is at index 0 inside the window, so left jumps to 1 and the window becomes bca. The same idea repeats for the second b and second c: the window does not restart, it slides past the old copy and keeps the longest valid suffix.
Algorithm
- Create a last-seen table where each character maps to the index after its latest occurrence.
- Start left = 0 and best = 0.
- For each right index, read the current character.
- Move left to max(left, lastSeenPlusOne[current]) so the previous copy is excluded only if it is inside the window.
- Update best with right - left + 1.
- Store right + 1 as the latest position for the current character.
- Return best.
Solutions
Solution: Last seen index sliding window
The last-seen table lets the left boundary jump over a duplicate in one step. Because left never moves backward, the window remains unique and the scan is linear.
Step-by-step
- Allocate an ASCII table where each entry stores one plus the last seen index, with 0 meaning unseen.
- Scan s from left to right with right.
- Before measuring the window, move left past the previous copy of the current character if that copy lies inside the active window.
- Update the best length using the current unique window.
- Record the current character position as right + 1 and continue.
O(n)
O(1)
Each character is processed once, and the ASCII table has fixed size 128.
Java implementation
Dry Run
Sample input
s = abcabcbb. Track left, right, the active unique window, and the best length.
| step | right char | left before | left after | window after update | best |
|---|---|---|---|---|---|
| 1 | a at 0 | 0 | 0 | a | 1 |
| 2 | b at 1 | 0 | 0 | ab | 2 |
| 3 | c at 2 | 0 | 0 | abc | 3 |
| 4 | a at 3 | 0 | 1 | bca | 3 |
| 5 | b at 4 | 1 | 2 | cab | 3 |
| 6 | c at 5 | 2 | 3 | abc | 3 |
| 7 | b at 6 | 3 | 5 | cb | 3 |
| 8 | b at 7 | 5 | 7 | b | 3 |
The best unique window length reaches 3 at abc and never improves afterward.
Interview Tips
Say that the key invariant is a duplicate-free window after every iteration. If using last indices, emphasize the max with the current left; without it, an old duplicate outside the window can incorrectly move left backward. If using a set, explain that the while loop removes characters until the duplicate is gone.
Likely follow-ups
- How would you return the actual longest substring instead of only the length?
- How would the solution change for full Unicode input instead of ASCII?
- How would you find the longest substring with at most **k** distinct characters?
- How would you process a stream where characters arrive one at a time?
Similar Problems
Key Takeaways
- Longest-valid windows expand right and repair invalidity by moving left.
- The invariant after each step is a window with no duplicate characters.
- Last-seen positions can jump **left** directly instead of shrinking one character at a time.
- **left** must never move backward.