25. Longest Substring Without Repeating Characters

mediumAsked at Coinbase

Find the longest run of unique trading-pair symbols in a sequence — Coinbase uses sliding-window problems to evaluate how you model streaming data with a shrinking-left-boundary technique common in real-time feed deduplication.

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

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: "abc" is the longest substring without repeats.

Example 2

Input

s = "bbbbb"

Output

Example 3

Input

s = "pwwkew"

Output

Explanation: "wke".

Approaches

1. Brute force (all substrings)

Check every pair of indices; for each, verify uniqueness via a Set. O(n^2).

Time: O(n^2)
Space: O(min(n, alphabet))

function lengthOfLongestSubstring(s) {
  let max = 0;
  for (let i = 0; i < s.length; i++) {
    const seen = new Set();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j])) break;
      seen.add(s[j]);
      max = Math.max(max, j - i + 1);
    }
  }
  return max;
}

Tradeoff:

2. Sliding window with last-seen map (optimal)

Map each character to its latest index. When a repeat is found, jump left to one past the duplicate's last position instead of shrinking one by one.

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

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map();
  let max = 0, left = 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:

Coinbase-specific tips

Coinbase evaluates whether you reach for the last-seen-map variant over the naive Set approach. The jump rather than step is the key insight: in a trading feed deduplication context, you never want to inch left one character at a time when you can skip straight to the conflict's origin. They also probe whether you handle the edge case where the last-seen index is before left — a subtle off-by-one that maps to stale-pointer bugs in ring-buffer implementations.

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 Coinbase interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →