#3
Longest Substring Without Repeating Characters
Medium Variable window
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the length of the longest substring with no repeated characters.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest stretch with no repeated letter.
Why this works: grow the window to the right; when a letter repeats, jump the left edge past its previous position.
Example: "abcabcbb"
"abc" length 3next 'a' repeats → left moves past first 'a' → "bca"… best stays 3
✦Hints open one at a time
Grow the window on the right; when a repeat appears, shrink from the left.
Remember the last index where each character was seen to jump the left edge directly.
↗Approach
Keep last[c] = latest index of c. When s[r] was seen at or after left, move left to last[c] + 1. The window left..r always has unique characters; record its length.
</>Solution (Java)
import java.util.*;
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] last = new int[128];
Arrays.fill(last, -1);
int left = 0, best = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
left = Math.max(left, last[c] + 1); // jump past the previous copy
last[c] = r;
best = Math.max(best, r - left + 1);
}
return best;
}
}!Common mistake
Moving left backwards when the previous occurrence is before the window. Use max(left, last + 1).
Complexity
- Time: O(n).
- Space: O(charset) — 128 for ASCII.
Topic: Sliding Window
🎬 Episode 10: video coming soon