32. Longest Substring Without Repeating Characters

mediumAsked at Datadog

Find the length of the longest substring with no repeating characters. Datadog asks this as the sliding-window foundation — the same pattern they use for windowed deduplication of streaming events.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Datadog loops.

Glassdoor (2026-Q1)— Datadog onsite — graded on sliding window.
Blind (2025-11)— Recurring Datadog problem.

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

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

Example 2

Input

s = "bbbbb"

Output

Example 3

Input

s = "pwwkew"

Output

Approaches

1. Brute-force check all substrings

Try every substring; check uniqueness with a Set.

Time: O(n^3)
Space: O(min(n, alphabet))

function lengthOfLongestSubstring(s) {
  let best = 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]);
      best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

Tradeoff: Cubic — won't survive a 50K input. Datadog will fail this.

2. Sliding window with last-index map (optimal)

Two pointers. Track last-index-seen of each char in a map. On a repeat, jump the left pointer past the previous occurrence.

Time: O(n)
Space: O(min(n, alphabet))

function lengthOfLongestSubstring(s) {
  const lastIdx = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (lastIdx.has(c) && lastIdx.get(c) >= left) {
      left = lastIdx.get(c) + 1;
    }
    lastIdx.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Tradeoff: Single pass. Each char visited at most twice. Datadog-canonical sliding-window pattern.

Datadog-specific tips

Datadog will follow up with: 'Now do it over a streaming character source where you can't look ahead.' Show that the sliding window already IS streaming-friendly — process char-by-char. They also probe on the 'last index >= left' check — articulate why it's needed (the char might have appeared OUTSIDE the current window).

Common mistakes

Forgetting the lastIdx.get(c) >= left check — would wrongly retract the left pointer for a char that's already outside the window.
Setting left = lastIdx.get(c) instead of lastIdx.get(c) + 1 — keeps the duplicate in the window.
Using a Set instead of a Map — forces O(window_size) left-pointer advancement instead of jump-ahead.

Follow-up questions

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

Longest Substring with At Most K Distinct Characters (LC 340).
Longest Substring with At Most Two Distinct Characters (LC 159).
Minimum Window Substring (LC 76).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why O(min(n, alphabet))?

The map can hold at most one entry per distinct character. For ASCII inputs, that's bounded by 128 regardless of n.

Is the window contiguous?

Yes — the question asks for a substring, which is contiguous. Substring ≠ subsequence.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →