Given a string s, return the length of its longest substring that contains no repeated character. Substring means contiguous — "pwke" inside "pwwkew" is a subsequence, not a substring, and does not count.
Examples
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: "abc", three characters, no repeats.
Example 2:
Input: s = "bbbbb"
Output: 1
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: "wke".
Example 4:
Input: s = "dvdf"
Output: 3
Explanation: "vdf" — the window must jump past the first d, not merely shrink by one.
Constraints
1 <= s.length <= 5 * 10^4
s consists of printable ASCII characters.
Prerequisites
Sliding windows — a left and right edge moving forward only, and the invariant that decides when the left edge advances. Hash maps or fixed-size counts for what the window currently holds.
How to think about it
1. Sliding Window With Last-Seen Positions Optimal
Intuition
A window with no repeats stays valid as long as the incoming character is new. When it is not, the left edge must jump to just past that character's PREVIOUS position — not merely one step right. Remembering where each character was last seen makes that jump O(1), and never letting the left edge move backwards is what keeps "dvdf" honest.
Algorithm
1. Keep a map from character to the index it was last seen at. 2. Extend the right edge one character at a time. 3. If that character was seen at or after the left edge, move left to one past it. 4. Record the character's new position and the window's width.
Time & Space
Time O(n) — each edge moves forward only. Space O(k) for the alphabet in play.