Skip to main content

3. Longest Substring Without Repeating Characters

mediumAsked at Linear

Find the length of the longest substring with no repeated characters. Linear uses this to test the sliding-window pattern — maintaining a valid window by shrinking the left pointer when a duplicate enters.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2026-Q1)— Frequently cited in Linear SWE phone screen and onsite reports.
  • Blind (2025-11)— Multiple Linear interview threads list this as a core sliding-window question.

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', with length 3.

Example 2

Input
s = "bbbbb"
Output
1

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

Example 3

Input
s = "pwwkew"
Output
3

Explanation: 'wke' has length 3. Note: 'pwke' is a subsequence, not a substring.

Approaches

1. Brute force all substrings

For each starting index, extend and check uniqueness; track the longest valid substring.

Time
O(n^2)
Space
O(min(m,n))
function lengthOfLongestSubstring(s) {
  let max = 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]);
      max = Math.max(max, j - i + 1);
    }
  }
  return max;
}

Tradeoff: O(n^2) with O(k) set per start. Correct but inefficient — use this to name the repeating-work problem before pivoting.

2. Sliding window with map (optimal)

Maintain a window [left, right]. Expand right; when a duplicate is found, jump left to just past the last occurrence of that character.

Time
O(n)
Space
O(min(m,n))
function lengthOfLongestSubstring(s) {
  const lastSeen = new Map();
  let left = 0;
  let max = 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);
    max = Math.max(max, right - left + 1);
  }
  return max;
}

Tradeoff: O(n) single pass. Storing the last seen index instead of a presence flag lets you jump left pointer directly, avoiding repeated increments. The guard lastSeen.get(ch) >= left ensures we don't move left backward.

Linear-specific tips

Linear interviewers test whether you can explain the sliding window invariant before coding it: 'At all times, the window [left, right] contains only unique characters.' Narrate what happens when a duplicate enters — jump left, not nudge left — and explain why storing the index (not just presence) enables the jump.

Common mistakes

  • Moving left one step at a time when a duplicate is found — O(n^2) behavior instead of the O(n) jump.
  • Not guarding against moving left backward — if lastSeen has an old index before the current window, you must not move left there.
  • Using a Set instead of a Map — then you can't jump left directly and must shrink character by character.

Follow-up questions

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

  • Longest Substring with At Most K Distinct Characters (LC 340) — generalize the window validity condition.
  • Minimum Window Substring (LC 76) — harder sliding window with character frequency constraints.
  • What if the string contains Unicode characters with multi-byte encodings?

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 use a Map over a Set?

A Map stores the last seen index, enabling a direct jump of the left pointer. A Set only stores presence — you'd have to move left one character at a time, giving O(n^2) behavior.

What does 'min(m, n)' mean in the space complexity?

m is the character set size (e.g., 26 for lowercase letters, 128 for ASCII). The map can hold at most min(m, n) entries since duplicate characters shrink the window.

What if the string is empty?

The loop doesn't execute; max stays 0. Correct, since an empty string has no substring.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →