Skip to main content

16. Longest Substring Without Repeating Characters

mediumAsked at Mercury

Find the length of the longest substring of a string with all distinct characters.

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

Problem

Given a string s, return the length of the longest substring containing no repeated characters. The substring must be contiguous; characters are case sensitive.

Constraints

  • 0 <= s.length <= 5*10^4
  • ASCII characters

Examples

Example 1

Input
s = 'abcabcbb'
Output
3

Example 2

Input
s = 'bbbbb'
Output
1

Approaches

1. Brute force all windows

Try every (i,j) substring and check uniqueness.

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

Tradeoff:

2. Sliding window with last-seen map

Expand right and jump the left pointer past the prior occurrence of any repeated character. Single pass.

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

Tradeoff:

Mercury-specific tips

Mercury asks sliding-window in the context of fraud-pattern detection — the longest distinct-merchant streak on a corporate card is exactly this problem with merchants in place of characters.

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

Practice these live with InterviewChamp.AI →