Skip to main content

3. Longest Substring Without Repeating Characters

mediumAsked at Anduril

Find the length of the longest substring with all unique characters. Anduril uses this classic sliding-window problem to test whether you can maintain a dynamic window with O(1)-lookup membership — the same pattern appears in rate-limiting command queues and deduplicating real-time event streams on autonomous platforms.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2025-12)— Anduril SWE onsite reports list this as a sliding-window medium question in early technical rounds.
  • Blind (2025-10)— Candidate reports from Anduril describe this problem as a common medium to probe two-pointer and hash-map fluency.

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 longest substring without repeating characters is 'abc'.

Example 2

Input
s = "bbbbb"
Output
1

Explanation: The longest valid substring is 'b' with length 1.

Example 3

Input
s = "pwwkew"
Output
3

Explanation: 'wke' is the longest unique substring.

Approaches

1. Sliding window with set

Maintain a window [left, right] of unique characters using a Set. When a duplicate is found, shrink from the left until the window is valid again.

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

Tradeoff: Clear and correct. Each character is added and removed from the set at most once, so the overall work is O(n) despite the nested while loop.

2. Sliding window with map (jump optimization)

Store the last-seen index of each character in a map. When a duplicate is found, jump left directly to lastSeen[char]+1 instead of shrinking one step at a time.

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

Tradeoff: Still O(n) but avoids the inner while loop by jumping left in one step. The >= left check ensures we don't move left backwards when a character's last occurrence is outside the current window.

Anduril-specific tips

State the sliding-window invariant before coding: 'I maintain a window [left, right] where every character is unique. When a duplicate enters from the right, I advance left until it's gone.' Anduril engineers appreciate when you name the pattern and explain the O(n) amortized cost of the two-pointer approach. The map-based jump is worth mentioning as an optimization, but be careful with the >= left guard — a common source of subtle bugs.

Common mistakes

  • Moving left without updating the window membership structure — the set or map becomes stale.
  • In the map approach, not checking lastIndex >= left — a character that was seen before the current window should not trigger a left jump.
  • Returning maxLen before updating it inside the loop — compute window size after adding s[right].
  • Not handling the empty string — s.length === 0 should return 0; most implementations handle this naturally.

Follow-up questions

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

  • Longest substring with at most K distinct characters (LC 340).
  • Minimum window substring (LC 76) — find the smallest window containing all characters of a target string.
  • How would you solve this for a stream where you can only look at the last W characters?

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 is the time complexity O(n) despite the while loop?

Each character is added to and removed from the set at most once across the entire traversal, so the total work across all iterations of both loops is O(n).

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

The window can hold at most m unique characters (the charset size, e.g. 128 for ASCII) or n characters (the string length), whichever is smaller.

Does the set or map approach generalize to unicode?

Yes — both Map and Set handle arbitrary keys including unicode code points.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →