3. Longest Substring Without Repeating Characters

mediumAsked at Citadel

Sliding window on a character stream is a core primitive in financial data processing — think deduplicating a stream of order IDs, finding the longest non-redundant price sequence, or scanning for unique symbol windows in tick data. Citadel uses this problem to verify you can implement an O(n) shrinkable window correctly.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

Glassdoor (2026-Q1)— Citadel SWE candidates report sliding-window string problems as a consistent category in first and second round coding assessments.
Blind (2025-11)— Citadel SWE threads list LC 3 as a high-frequency question that tests the sliding-window pattern interviewers consider foundational.

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

Example 2

Input

s = "bbbbb"

Output

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

Example 3

Input

s = "pwwkew"

Output

Explanation: The answer is 'wke', with the length of 3.

Approaches

1. Sliding window with Map (jump-ahead)

Maintain a window [left, right] and a Map from character to its most recent index. When a duplicate is found, jump left directly to max(left, lastSeen + 1) rather than shrinking one step at a time.

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

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

Tradeoff: True O(n) — each character is visited once by the right pointer. The Map stores the last seen index, enabling an O(1) jump of left. This is the most performant variant and the expected answer.

2. Sliding window with Set (shrink one step at a time)

Expand right; when a duplicate is found, shrink left one character at a time until the window is valid again.

Time: O(n) amortized — each char added and removed at most once
Space: O(min(n, charset))

function lengthOfLongestSubstring(s) {
  const window = new Set();
  let maxLen = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    while (window.has(s[right])) {
      window.delete(s[left++]); // shrink from left
    }
    window.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Tradeoff: Amortized O(n) but may take multiple left-shrink steps per iteration. Simpler to reason about but slower in practice than the jump-ahead Map version. Mention both and lead with the Map approach.

Citadel-specific tips

State the sliding-window invariant before coding: 'At every step, window [left, right] contains only unique characters.' Then explain the two variants: Set shrinks one step at a time; Map jumps left directly. At Citadel's performance bar, the Map jump-ahead is preferred. Also mention: 'For ASCII-only input (128 chars) I could use a fixed-size Int32Array instead of a Map, eliminating hash overhead — important at microsecond latency.' Expect: 'What if we need the actual substring, not just its length?' Track left at the point of maxLen update.

Common mistakes

Forgetting the lastSeen.get(ch) >= left guard — without it, you might jump left backward to a stale index from before the current window.
Initializing left to -1 or using 1-based indexing — causes off-by-one in the window length calculation (right - left + 1).
Using a simple boolean array indexed by char code without resetting on window shrink — stale 'true' values cause false duplicate detection.
Not handling empty string (s.length === 0) — the loop doesn't execute and maxLen returns 0 correctly, but verify this explicitly.

Follow-up questions

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

Longest Substring with At Most K Distinct Characters (LC 340) — generalize the Map to allow k distinct chars.
Minimum Window Substring (LC 76) — find the smallest window containing all chars of a target.
How would you implement this for a streaming data source where the full string isn't known upfront?

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 lastSeen >= left guard matter?

A character's last-seen index might be before the current left boundary — meaning it's no longer in the window. Without the guard, you'd incorrectly jump left backward, shrinking the window unnecessarily.

What is the space complexity for a Unicode input?

Up to O(n) for arbitrary Unicode since there's no fixed charset size. For ASCII-only input, O(128) — a fixed constant.

Is this problem ever O(n²)?

The Set approach is O(n²) in the worst case only if you re-shrink every step (e.g., 'aaaa...a'). Amortized it's O(n) because each char is added and deleted at most once. The Map approach is strictly O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →