Skip to main content

9. Longest Substring Without Repeating Characters

mediumAsked at Autodesk

Find the length of the longest substring without repeating characters.

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 letters, digits, symbols and spaces

Examples

Example 1

Input
s="abcabcbb"
Output
3

Example 2

Input
s="bbbbb"
Output
1

Approaches

1. All substrings

Enumerate every substring, check uniqueness with a set.

Time
O(n^3)
Space
O(n)
for (let i=0;i<n;i++)
  for (let j=i;j<n;j++) {
    if (allUnique(s,i,j)) best=Math.max(best,j-i+1);
  }

Tradeoff:

2. Sliding window

Expand a right pointer; on a repeat, shrink the left until the window is unique again. Each index moves at most twice.

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

Tradeoff:

Autodesk-specific tips

Sliding window discipline carries over to Autodesk's streaming geometry buffers and sweep-line algorithms used in CAD intersection tests.

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

Practice these live with InterviewChamp.AI →