Skip to main content

23. Longest Substring Without Repeating Characters

mediumAsked at Spotify

Find the longest window of unique characters in a string — the sliding-window technique translates directly to computing rolling unique-listener counts across a time-series of Spotify stream events.

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

Problem

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

Constraints

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

Examples

Example 1

Input
s = "abcabcbb"
Output
3

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

Example 2

Input
s = "bbbbb"
Output
1

Example 3

Input
s = "pwwkew"
Output
3

Approaches

1. Brute force

Check every substring for uniqueness using a set; track the maximum length found.

Time
O(n^3)
Space
O(min(n, m)) where m is charset size
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 map

Maintain a left pointer and a map of character-to-last-seen-index; when a repeat is found, jump the left pointer past the previous occurrence. Single pass.

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

Tradeoff:

Spotify-specific tips

Spotify evaluates this problem on two axes: correctness and communication. Narrate the window-shrink decision aloud — 'I'm moving left past the duplicate because I need the window to stay valid' — the way a data engineer would explain a deduplication step in a stream-processing pipeline.

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

Practice these live with InterviewChamp.AI →