Skip to main content

3. Longest Substring Without Repeating Characters

mediumAsked at eBay

eBay's search autocomplete and suggestion engine needs to deduplicate character sequences in query strings efficiently. This sliding-window problem is a medium staple in eBay's onsite loop because it requires coordinating a Set and two pointers to achieve O(n) — a clean test of sliding-window mastery before harder variants.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2026-Q1)— Listed as one of the most common eBay medium problems across phone screens and first onsite rounds.
  • Blind (2025-12)— eBay SWE candidates consistently cite this as a sliding-window must-practice for the interview loop.

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 the length of 3.

Example 2

Input
s = "bbbbb"
Output
1

Explanation: The answer is 'b', with the length of 1.

Example 3

Input
s = "pwwkew"
Output
3

Explanation: The answer is 'wke', with the length of 3. Notice that 'pwke' is not a substring.

Approaches

1. Sliding Window with Set

Maintain a window [left, right] where all characters are unique. Expand right; when a duplicate is found, shrink from the left until the duplicate is removed.

Time
O(n)
Space
O(min(m, n)) where m is charset size
function lengthOfLongestSubstring(s) {
  const window = new Set();
  let left = 0, maxLen = 0;
  for (let right = 0; right < s.length; right++) {
    while (window.has(s[right])) {
      window.delete(s[left]);
      left++;
    }
    window.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Tradeoff: O(n) amortized — each character is added and removed at most once. The Set approach is intuitive and easy to reason about.

2. Sliding Window with last-seen Map (optimized)

Store the most recent index of each character. When a duplicate is found, jump left directly to the position after the last occurrence — avoiding character-by-character shrinking.

Time
O(n)
Space
O(min(m, n))
function lengthOfLongestSubstring(s) {
  const lastSeen = new Map(); // char → last index
  let left = 0, maxLen = 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; // jump past the duplicate
    }
    lastSeen.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Tradeoff: O(n) with smaller constant — left pointer jumps instead of steps, eliminating the inner while loop. The check lastSeen.get(s[right]) >= left is critical: without it, you'd jump left backward.

eBay-specific tips

eBay interviewers appreciate the transition from the Set-based approach to the Map-based jump. Explain: 'The Set approach is O(n) amortized but has an inner while loop. With a Map, I can jump left directly.' The condition >= left matters — if a character was last seen before the window started, that old index is irrelevant. Draw the window state for 'abcabcbb' before coding.

Common mistakes

  • Forgetting the >= left guard in the Map approach — causes left to jump backward, expanding the window incorrectly.
  • Computing window length as right - left (off by one) instead of right - left + 1.
  • Using s.charAt(right) vs s[right] inconsistently — both work in JavaScript but be consistent.
  • Not handling the empty string case — the loop simply doesn't execute and maxLen returns 0 correctly, but verify this mentally.

Follow-up questions

An interviewer at eBay may pivot to one of these next:

  • Longest Substring with At Most K Distinct Characters (LC 340) — generalize the window to allow k unique characters.
  • Minimum Window Substring (LC 76) — find the smallest window containing all characters of a target string.
  • How would you find the actual substring, not just its length?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What does O(min(m, n)) space mean?

m is the size of the character set (e.g., 128 for ASCII, 26 for lowercase letters). The Set/Map holds at most min(m, n) entries — bounded by both the string length and the charset.

Is the Set approach strictly worse than the Map approach?

In the worst case (all identical characters) the inner while loop runs O(n) per character, but amortized over all characters it's still O(n). The Map approach has better constant factors but the same asymptotic complexity.

Why can't you use a fixed-size array instead of a Map?

You can — an array of size 128 (ASCII) or 256 (extended ASCII) storing last-seen indices works and avoids Map overhead. Mention this as an optimization for known-charset inputs.

Practice these live with InterviewChamp.AI

Drill Longest Substring Without Repeating Characters and other eBay interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →