Mid · Sliding window

Longest Substring without Repeats

Return the length of the longest contiguous substring with no repeated characters. Input is ASCII; the empty string returns 0. Describe what makes your current window valid.

Examples

"abcabcbb" → 3

"abba" → 2

Compare approaches

Restart at every index

Start a fresh set at each index and stop at the first duplicate.

Time: O(n²) upper bound · Space: O(min(n, alphabet size))

function longestUnique(text) { let best = 0; for (let i = 0; i < text.length; i++) { const seen = new Set(); for (let j = i; j < text.length && !seen.has(text[j]); j++) { seen.add(text[j]); best = Math.max(best, j - i + 1); } } return best; }

Last-seen sliding window

Move left beyond a repeated character without moving backwards; each right endpoint is visited once.

Time: O(n) expected · Space: O(min(n, alphabet size))

function longestUnique(text) {
  const last = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < text.length; right++) {
    if (last.has(text[right])) left = Math.max(left, last.get(text[right]) + 1);
    last.set(text[right], right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Common traps

Use Math.max so an old occurrence cannot move left backwards.
A subsequence is not necessarily contiguous.

Practise in the workspace →