3. Longest Substring Without Repeating Characters

Return the length of the longest substring of s that contains no repeated characters.

Remember the last index of each character. On a repeat, jump lo straight past the previous occurrence instead of removing characters one by one.

1function lengthOfLongestSubstring(s: string): number {
2  const last = new Map<string, number>();
3  let lo = 0, best = 0;
4  for (let hi = 0; hi < s.length; hi++) {
5    if (last.has(s[hi]) && last.get(s[hi])! >= lo) lo = last.get(s[hi])! + 1;
6    last.set(s[hi], hi);
7    best = Math.max(best, hi - lo + 1);
8  }
9  return best;
10}

s

Empty map.

1 / 0

Space: play/pause · ←/→: step