Longest Substring Without Repeating Characters

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}