Longest Substring Without Repeating Characters
Medium· variable window· hash map
Problem
Return the length of the longest substring in which no character appears more than once.
Examples
Input: s = "abcabcbb"
Output: 3
"abc" is the longest repeat-free substring.
Input: s = "pwwkew"
Output: 3
"wke" works; "pwke" is not contiguous, so it does not count.
Constraints
- • 0 <= s.length <= 5 * 10^4
- • s may contain letters, digits, symbols and spaces
Hints & approach
Hint 1
Grow a window to the right as long as it stays valid.
Hint 2
When a repeat enters, shrink from the left until it is gone.
Hint 3
Remembering the last index of each character lets the left edge jump directly.
Approachtry the hints first
Keep a map from each character to the last index where it was seen, and a left boundary start. For each index end, if the character was last seen at or after start, move start to one past that index. Update the character's last index and record end - start + 1 as a candidate answer. The left edge only moves forward, so the scan is linear.
Time O(n) · Space O(min(n, alphabet))