Longest Substring Without Repeating Characters
Walkthrough video coming soon
The full explanation is written out below — the problem, the intuition, the approach, and the solution code.
The problem
Given a string `s`, find the length of the longest substring that contains no repeating characters.
Constraints & assumptions
- 0 ≤ s.length ≤ 5·10⁴
- s consists of English letters, digits, symbols and spaces
In plain English
Think of dragging a highlighter across the text, marking a stretch of characters. The rule: your highlighted stretch may never contain the same character twice. You keep extending the right edge, greedily grabbing more.
The instant you'd cover a character that's already inside the highlight, you slide the left edge forward until the duplicate is gone — the window shrinks just enough to stay valid, then keeps growing. The longest the highlight ever gets is your answer. That growing-and-shrinking window is the whole technique.
What you need to know
The programming concepts this problem is built on:
How to approach it
- 1Maintain a window [left … right] that only ever holds unique characters.
- 2Advance the right edge one character at a time.
- 3If the new character already sits inside the window, move the left edge past its previous position.
- 4After each step, update the best length with the current window size.
The solutions
2 waysThis one can be solved more than one way. Switch between the methods to compare — each summary explains how it differs.
Shrink the window one step at a time using a HashSet.
A set holds exactly the characters currently in the window. On a duplicate, we remove characters from the left one by one until the clash is gone. Simple and easy to reason about; the left pointer may take several small steps.
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> window = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
while (window.contains(s.charAt(right))) {
window.remove(s.charAt(left));
left++;
}
window.add(s.charAt(right));
best = Math.max(best, right - left + 1);
}
return best;
}
}