Longest Substring Without Repeating Characters
MediumSliding window
Given a string s, return the length of its longest substring, a run of consecutive characters, in which no character appears twice.
Examples
Input: s = "xyzxyy" Output: 3
xyz, yzx and zxy are the longest runs without a repeat.
Input: s = "aaaa" Output: 1
Any run longer than one character repeats the a.
Constraints
0 ≤ s.length ≤ 5 × 10⁴scan hold letters, digits, symbols and spaces.
Stuck?
Hint 1
Keep a window of characters with no repeat, and extend it to the right one character at a time.
Hint 2
When the new character is already in the window, move the left edge just past its last position. A Map of last positions makes that a jump instead of a walk.
The idea
Keep a window, from start up to the current character, with no repeat in it. Each new character extends the window on the right. When that character is already inside the window, the left edge jumps past its earlier copy, and the longest window seen along the way is the answer.
Time O(n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
last remembers where each character was seen most recently. start is the left edge of the window.
function lengthOfLongestSubstring(s) { const last = new Map(); let start = 0; let best = 0; for (let i = 0; i < s.length; i++) { if (last.has(s[i]) && last.get(s[i]) >= start) { start = last.get(s[i]) + 1; } last.set(s[i], i); best = Math.max(best, i - start + 1); } return best;}The trap
It moves start past the last copy of a repeated character even when that copy is already outside the window. When characters repeat in order the jump is always forward, so most strings pass. But when an inner pair of repeats sits inside an outer pair, the outer repeat pulls start backwards, and the window grows over a repeat it had already left behind.
function lengthOfLongestSubstring(s) { const last = new Map(); let start = 0, best = 0; for (let i = 0; i < s.length; i++) { if (last.has(s[i])) start = last.get(s[i]) + 1; // can move the window back last.set(s[i], i); best = Math.max(best, i - start + 1); } return best;}