3. Longest Substring Without Repeating Characters

mediumAsked at DRW

DRW uses this problem to test the sliding-window pattern — the same technique that powers rolling-window deduplication on market-data feeds and tick-data deduplication in low-latency pipelines. Getting to O(n) with a single hash-map pass is required; naive O(n²) solutions are rejected on sight.

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

Glassdoor (2026-Q1)— DRW SWE candidates report sliding-window string problems as a common medium-difficulty question in phone and first onsite rounds.
Blind (2025-10)— DRW interview threads cite this problem as a must-prepare medium, with interviewers specifically asking for the O(n) hash-map solution over naive approaches.

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

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

Example 3

Input

s = "pwwkew"

Output

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

Approaches

1. Sliding window with hash map

Expand the right pointer. If the character at right is already in the window, jump the left pointer to one past the last occurrence of that character. Track the maximum window size.

Time: O(n)
Space: O(min(n, |charset|))

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map(); // char -> last index
  let left = 0, maxLen = 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);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Tradeoff: Single pass, O(n) time. The key insight: when a repeat is found, jump left directly past the duplicate using the stored index — no need to shrink the window one step at a time.

2. Sliding window with Set

Use a Set to track characters in the current window. When a repeat is found, remove characters from the left until the duplicate is gone.

Time: O(n) amortized
Space: O(min(n, |charset|))

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 enters and leaves the Set at most once). Simpler to reason about but the inner while loop may cause more Map operations than the hash-map version. DRW prefers the hash-map version for its O(n) strict bound.

DRW-specific tips

DRW interviewers will ask: 'What if the string is a live character stream arriving at 100k characters per second and you need the rolling answer at every position?' The hash-map approach is already streaming-compatible — you output right − left + 1 at every step. They also ask: 'What is the expected longest non-repeating substring for a length-n string over an alphabet of size k?' The answer involves coupon-collector intuition: approximately k × H_k characters, where H_k is the k-th harmonic number.

Common mistakes

Not checking that lastSeen.get(ch) >= left before jumping — the old occurrence may be to the left of the current window.
Using the naive O(n²) approach with a Set reset on each new left pointer position.
Off-by-one in window size calculation — it is right − left + 1, not right − left.
Not handling the empty string — maxLen initialized to 0 correctly handles this.

Follow-up questions

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

Longest Substring with At Most Two Distinct Characters (LC 159) — generalize the window constraint.
Minimum Window Substring (LC 76) — find the smallest window containing all characters of a target string.
What is the expected length of the longest non-repeating substring over a uniformly random string of length n with alphabet size k?

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 does the hash-map version not need a while loop?

The map stores the last-seen index. When a duplicate is found, you can jump left directly to lastSeen[ch] + 1, skipping all intermediate positions at once. The Set version shrinks one step at a time, requiring the while loop.

What if the character set is fixed (e.g., ASCII)?

Replace the Map with a 128-element integer array indexed by character code. Constant-factor improvement: array access is faster than hash-map lookup.

Why does this appear in market-data pipelines?

Rolling deduplication on tick IDs uses the same sliding-window logic: track the last-seen position of each ID, advance the window left when a duplicate arrives.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →