Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters is a medium Sliding Window problem from the Blind 75. The key pattern is sliding window, and a good solution runs in O(n) time.
Problem
Return the maximum length of a substring containing no repeated character.
Examples
Example 1
Input
"telescope"Output
6Example 2
Input
"xyzxyzz"Output
3Example 3
Input
""Output
0Approach
Grow the window to the right and remember the last index of each character. When a repeat appears inside the window, jump the left edge just past its previous position.
| Pattern | Sliding window |
|---|---|
| Time | O(n) |
| Space | O(alphabet) |
Watch out for
Never move the left edge backwards; take the maximum of its current place and the jump target.