21. Longest Substring Without Repeating Characters

mediumAsked at Notion

Find the longest window of unique characters using a sliding pointer — Notion applies the same shrink-when-invalid pattern to its rich-text tokenizer, advancing a cursor only while the token stream stays well-formed.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Given a string s, find the length of the longest substring without duplicate characters.

Constraints

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols, and spaces

Examples

Example 1

Input

s = "abcabcbb"

Output

Explanation: The answer is "abc", length 3.

Example 2

Input

s = "bbbbb"

Output

Explanation: The answer is "b", length 1.

Approaches

1. Sliding window with Set

Expand right pointer; if char already in window set, shrink from left until it's gone. Track max window size.

Time: O(2n) = O(n)
Space: O(min(n, charset))

function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0;
  let max = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    max = Math.max(max, right - left + 1);
  }
  return max;
}

Tradeoff:

2. Sliding window with last-seen Map (optimal jump)

Store the last index of each character; on duplicate, jump left pointer directly to max(left, lastSeen[char] + 1) — at most one pass through the string.

Time: O(n)
Space: O(min(n, charset))

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map();
  let left = 0;
  let max = 0;
  for (let right = 0; right < s.length; right++) {
    if (lastSeen.has(s[right]) && lastSeen.get(s[right]) >= left) {
      left = lastSeen.get(s[right]) + 1;
    }
    lastSeen.set(s[right], right);
    max = Math.max(max, right - left + 1);
  }
  return max;
}

Tradeoff:

Notion-specific tips

Notion's inline mention parser must scan rich text for repeated inline elements without backtracking on every keystroke. Interviewers here will push you on why the jump-to-last-seen optimization is safe — be ready to prove left never moves backward.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Longest Substring Without Repeating Characters and other Notion interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →