Skip to main content

3. Longest Substring Without Repeating Characters

mediumAsked at Glean

Glean asks this to test sliding-window fluency — the same technique used in tokenizing and windowing text streams for indexing, where you need to identify the longest unique n-gram span without repetition.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2026-Q1)— Consistently mentioned in Glean onsite reports as the most common medium-level string problem.
  • Blind (2025-12)— Multiple Glean threads rank this as the #1 most asked medium in Glean phone screens and onsites.

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 answer is 'abc', with a length of 3.

Example 2

Input
s = "bbbbb"
Output
1

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

Example 3

Input
s = "pwwkew"
Output
3

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

Approaches

1. Sliding window with a Set

Maintain a window [left, right] and a Set of characters in the window. Expand right; when a duplicate is found, shrink from left until the duplicate is removed.

Time
O(n)
Space
O(min(n, m)) where m is the character set size
function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0, 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: O(n) time. Each character is added and removed from the set at most once. Simple and easy to explain.

2. Sliding window with a Map (optimized jump)

Store each character's most recent index in a Map. When a duplicate is found, jump left directly past the last occurrence instead of shrinking one step at a time.

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

Tradeoff: Still O(n) but with a smaller constant — no inner while loop. The index comparison `>= left` is critical: a character's stored index might be outside the current window (before left), so you only jump if the stored index is within range.

Glean-specific tips

Name the pattern: 'I'll use a sliding window.' Then explain what the window invariant is: 'The window always contains unique characters.' Glean engineers appreciate invariant-first thinking. Prefer the Map-based approach as your primary solution — it shows you understand why jumping is safe, not just that it's faster.

Common mistakes

  • Shrinking the window past the duplicate's last-known position — can make left go backward if lastIndex.get(s[right]) < left; always use Math.max(left, lastIndex.get(s[right]) + 1).
  • Counting window size as right - left instead of right - left + 1 — off-by-one error.
  • Not handling the empty string — returns 0 correctly from the Map approach since the loop never executes.
  • Assuming only lowercase letters — the constraint says the string can contain any character; a Map handles any character set.

Follow-up questions

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

  • Longest Substring with At Most Two Distinct Characters (LC 159) — generalize the uniqueness constraint.
  • Minimum Window Substring (LC 76) — a harder sliding-window problem with a target character count.
  • How does the approach change if you need to return the actual substring, not just its length?

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 must you check lastIndex.get(s[right]) >= left in the Map approach?

A character's stored index might be before the current left pointer — it's outside the window and not a real duplicate. Without this check, you'd incorrectly move left backward.

Is the Set approach or Map approach better to present first?

Present the Set approach first to establish correctness, then mention the Map optimization. This shows you can articulate a clean solution and know how to improve it.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →