Longest Substring Without Repeating Characters
Problem
Return the length of the longest substring (contiguous) that contains no repeated character.
Example 1
Input: "abcabcbb" Output: 3
"abc".
Example 2
Input: "pwwkew" Output: 3
"wke" — "pwke" is a subsequence, not a substring.
Test cases
Case 1
Input: "abcabcbb" Expected: 3
Case 2
Input: "bbbbb" Expected: 1
Case 3
Input: "pwwkew" Expected: 3
Case 4
Input: "" Expected: 0
Case 5
Input: "abba" Expected: 2
View solutionHide solution2 approaches
1. Window with a set
Time O(n)Space O(alphabet)
Grow right; while the new char is already in the window, remove from the left.
function lengthOfLongestSubstring(s) { const win = new Set(); let l = 0, best = 0; for (let r = 0; r < s.length; r++) { while (win.has(s[r])) win.delete(s[l++]); win.add(s[r]); best = Math.max(best, r - l + 1); } return best;}2. Jump using last-seen index
Time O(n)Space O(alphabet)
Store each char’s last index; on a repeat inside the window, jump l straight past it.
function lengthOfLongestSubstring(s) { const last = new Map(); let l = 0, best = 0; for (let r = 0; r < s.length; r++) { if (last.has(s[r]) && last.get(s[r]) >= l) l = last.get(s[r]) + 1; last.set(s[r], r); best = Math.max(best, r - l + 1); } return best;}