Longest Substring Without Repeating Characters
Find the length of the longest substring without repeating characters.
Examples
"abc" is the longest stretch with no repeated character, so the answer is 3.
Every character is "b", so no stretch longer than 1 avoids a repeat.
"wke" is the longest repeat-free stretch, length 3. "pwke" does not count: its letters are not contiguous in the input, so it is a subsequence rather than a substring.
Problem Understanding
We need to find the length of the longest substring in a given string s that contains no duplicate characters.
A substring is a contiguous sequence of characters. For example, in "abcabcbb", "abc" is a substring, but "acb" is not (it skips characters).
Algorithm Strategy
We use the Sliding Window technique with a Hash Map (or Array for fixed charsets) to track characters in the current window.
- Initialize
left = 0andmax_len = 0. - Use a
mapto store the most recent index of each character. - Iterate
rightfrom 0 to end of string:- If
s[right]is inmapand its index is>= left, it means we found a repeat inside our current window. Movelefttomap[s[right]] + 1to skip the previous occurrence. - Update
map[s[right]]to the currentrightindex. - Update
max_len = max(max_len, right - left + 1).
- If
- Return
max_len.
Key Insight: Instead of shrinking the window one character at a time, we can jump the left pointer directly past the duplicate. Both versions are O(N); the jump just skips the inner shrinking loop.
Interactive Visualization
"dvdf"
EMPTY WINDOW
0
1
2
3
left
0
right
—
Length
—
Best
0
map (char:last index)
Empty
left starts at 0, the map is empty and the best length is 0
Next
Read 'd' at 0
String
Legend & Complexity
Solid frame: the window between L and R
Dashed frame: the character just read repeats inside it
The earlier copy that left jumps past
Characters before L
A map entry before L: still stored, no longer counts
Time
O(n)
Space
O(min(n, charset))
Watch how the window expands and jumps the left pointer when a duplicate is found.
Dry Run: s = "dvdf"
| Step | Window | Char | Map State | Action |
|---|---|---|---|---|
| 1 | "" |
d | {} |
New char. Add 'd'. Window: "d". Max=1. |
| 2 | "d" |
v | {d:0} |
New char. Add 'v'. Window: "dv". Max=2. |
| 3 | "dv" |
d | {d:0, v:1} |
Duplicate 'd'! Old 'd' at idx 0. Move Left to 0+1=1. Update 'd' idx to 2. Window: "vd". |
| 4 | "vd" |
f | {d:2, v:1} |
New char. Add 'f'. Window: "vdf". Max=3. |
| End | Result: 3 |
Edge Cases & Common Mistakes
Edge Cases:
- Empty String: Return 0.
- Single Character: Return 1.
- All Duplicates: "aaaa" -> Return 1.
- No Duplicates: "abcdef" -> Return length of string.
Common Mistakes:
- Not checking if duplicate is in active window: You might see a char that appeared way before
left. Ensuremap[char] >= leftbefore movingleft. - Subsequence vs Substring: Confusing contiguous substring with non-contiguous subsequence.
Solution
Optimized Sliding Window using a Hash Map for O(1) lookups.
Longest Substring Without Repeating Characters Code
1/**2 * @param {string} s3 * @return {number}4 */5var lengthOfLongestSubstring = function(s) {6 let seen = new Map();7 let left = 0;8 let maxLen = 0;910 for (let right = 0; right < s.length; right++) {11 let char = s[right];12 if (seen.has(char) && seen.get(char) >= left) {13 left = seen.get(char) + 1;14 }15 seen.set(char, right);16 maxLen = Math.max(maxLen, right - left + 1);17 }18 return maxLen;19};