Longest Substring Without Repeating Characters medium
Description
Given a string s, find the length of the longest substring without repeating characters.
Examples
> Case 1:
s = "abcabcbb"
Output: 3
Explanation: the answer is "abc" with length 3.
> Case 2:
s = "bbbbb"
Output: 1
Explanation: the answer is "b".
> Case 3:
s = "pwwkew"
Output: 3
Explanation: the answer is "wke" — note that "pwke" is a SUBSEQUENCE, not a substring.Constraints
0 <= s.length <= 5 × 10^4sconsists of English letters, digits, symbols, and spaces.
State design
- Contiguous range? Yes — substring.
- Monotone in growth? Yes — adding a character can only push the “has duplicate” predicate from false to true, never back.
- State? Set of characters in the current window.
- Shrink rule? While the just-added character is already in the set.
- When to record? After the shrink — the window is valid;
r − l + 1is a candidate longest.
Code — set version
Time: O(n). Space: O(min(n, charset)).
Optimization — “skip ahead” with a hash map
The set-based version may shrink l one step at a time. We can do better: track each character’s last seen index in a hash map, and on a duplicate, jump l directly past the previous occurrence.
Same O(n) worst case, but each character is visited exactly once (instead of potentially k times during a shrink). For most inputs the difference is invisible; on pathological inputs (“aaaaaaa…aaab”) it matters.
The last[c] >= l guard is critical: if the character’s previous occurrence is before the current window’s left edge, it isn’t a “duplicate in the window” — it’s just an old memory. Skipping that check causes l to jump backwards in some cases, breaking the algorithm.
Analysis
- Time:
O(n). - Space:
O(min(n, charset size)).
Same skin
- Longest Substring with At Most K Distinct Characters — same template, frequency map instead of set, “shrink while distinct count > k”.
- Longest Repeating Character Replacement — same template plus a “max frequency” tracker.
- Fruit Into Baskets — at most 2 distinct, otherwise identical.