Skip to main content

16. Longest Substring Without Repeating Characters

mediumAsked at Yelp

Find the length of the longest substring with all distinct characters — Yelp uses this sliding-window pattern to test whether candidates can scale to deduping review n-grams.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string s, find the length of the longest substring without repeating characters. Substrings must be contiguous.

Constraints

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

Examples

Example 1

Input
s = "abcabcbb"
Output
3

Example 2

Input
s = "bbbbb"
Output
1

Approaches

1. Brute force

Check every substring for distinct characters.

Time
O(n^3)
Space
O(min(n, k))
let best = 0;
for (let i = 0; i < s.length; i++)
  for (let j = i; j < s.length; j++) {
    const sub = s.slice(i, j+1);
    if (new Set(sub).size === sub.length) best = Math.max(best, sub.length);
  }
return best;

Tradeoff:

2. Sliding window with last-seen map

Track the last index where each character appeared and jump the left pointer past any repeat.

Time
O(n)
Space
O(k)
function lengthOfLongestSubstring(s) {
  const last = new Map();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    if (last.has(s[r]) && last.get(s[r]) >= l) l = last.get(s[r]) + 1;
    last.set(s[r], r);
    best = Math.max(best, r - l + 1);
  }
  return best;
}

Tradeoff:

Yelp-specific tips

Yelp will pivot to review fraud — be ready to discuss how a sliding-window dedup window flags reviews where the same phrase repeats across submissions from the same IP block.

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

Practice these live with InterviewChamp.AI →