0
L
Find the length of the longest substring with no repeated characters by keeping a sliding window whose left edge jumps past any duplicate the moment R would let one in — one pass, O(n).
Given a string s, return the length of the longest substring that contains no duplicate characters. s="abcabcbb": the answer is 3 — the window "abc" (indices 0–2). When R hits the second 'a' at index 3, the window must shrink. For s="bbbbb" the answer is 1; for s="pwwkew" it is 3 ("wke").
[L, R] that always contains unique characters. When s[R]would create a duplicate, don't slide L one step at a time — jump it directly past the previous occurrence of the duplicate. A Map<char, lastIndex> makes that jump O(1), so the whole pass is O(n).L=0, best=0, empty lastSeen map (char → most recent index).R through every character. This is the driver — we always try to grow.lastSeen has s[R] at index prev and prev >= L(it's still inside our window), jump: L = prev + 1. The >= L guard prevents accidentally pulling L backwards if the map has a stale entry from before the current window.lastSeen[s[R]] = R (always, whether or not we jumped). Then best = max(best, R−L+1).prev >= L guard. If a character appeared before the current window starts, its stale map entry must be ignored — otherwise L could move backwards and allow duplicates back in. Always confirm the collision is inside the live window.The map holds at most min(n, |alphabet|) entries — O(1) for a fixed alphabet (e.g. ASCII 128). A Set works too but requires sliding L one step at a time until the duplicate leaves, giving the same O(n) total but more iterations per collision.
L=0, scan R left-to-right.function lengthOfLongestSubstring(s: string): number {
const lastSeen = new Map<string, number>();
let L = 0;
let best = 0;
for (let R = 0; R < s.length; R++) {
const prev = lastSeen.get(s[R]);
if (prev !== undefined && prev >= L) {
// s[R] repeats inside the current window — jump L past it
L = prev + 1;
}
lastSeen.set(s[R], R); // record / update last-seen index
best = Math.max(best, R - L + 1);
}
return best;
}lastSeen maps each character to the last index where it appeared. This is what lets us jump L in O(1) instead of creeping forward step by step.L is the left edge of the current valid window; best records the maximum window length seen so far.s[R] already appears inside [L, R-1], move L directly to prev + 1. The prev >= L guard is critical: without it a character last seen before the window would drag L backwards.s[R], even after a jump (the character is now the rightmost element of the window). Then update best.R advances exactly n times; L only moves right so across all iterations it also advances at most n times → 2n total pointer moves. O(min(n, |alphabet|)) space for the map.bestL alongside best and return s.slice(bestL, bestL + best).L whenever map.size > k.s[L] !== s[R] advancing L. Same O(n) amortised, but each collision can require O(window) inner loop steps; the map's O(1) jump is cleaner.| "longest substring / subarray with no repeats" | sliding window + last-seen map |
| need O(1) jump of left pointer on collision | Map<char, lastIndex> + L = prev+1 |
| "at most k distinct characters" | sliding window + frequency map, shrink when size > k |
| stale map entry outside window | guard: only jump when prev >= L |
const lastSeen = new Map<string, number>();
let L = 0, best = 0;
for (let R = 0; R < s.length; R++) {
const prev = lastSeen.get(s[R]);
if (prev !== undefined && prev >= L) {
L = prev + 1; // shrink: jump past the duplicate
}
lastSeen.set(s[R], R); // update last-seen position
best = Math.max(best, R - L + 1);
}
return best;L jump past a collision in O(1) instead of creeping forward one step at a time."abcabcbb"?s="abcabcbb" up through index R=3 (the second 'a'), where does L land?