Skip to main content

3. Longest Substring Without Repeating Characters

mediumAsked at Gusto

Find the length of the longest substring with all unique characters. Gusto asks this as a sliding-window archetype — they want to see a clean window-shrink step that jumps the left pointer past the duplicate, not just nudges it one step.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2026-Q1)— Frequently cited in Gusto phone-screen and onsite reports as the canonical sliding-window medium.
  • Blind (2025-11)— Gusto SWE threads list this as a high-frequency problem with follow-ups on ASCII vs Unicode character sets.

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 substring 'abc' has length 3.

Example 2

Input
s = "bbbbb"
Output
1

Explanation: All characters are the same; longest unique window is any single 'b'.

Example 3

Input
s = "pwwkew"
Output
3

Explanation: The substring 'wke' has length 3.

Approaches

1. Sliding window with last-seen index map

Expand the right pointer character by character. If the character was seen within the current window, jump left to one past its previous position. Track maximum window size.

Time
O(n)
Space
O(min(n, charset))
function lengthOfLongestSubstring(s) {
  const lastSeen = new Map(); // char -> last index seen
  let maxLen = 0;
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    // if seen and within the current window, jump left past it
    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 last-seen index approach allows the left pointer to jump directly rather than step one at a time, which is more efficient in practice.

2. Sliding window with a Set

Maintain a Set of characters in the current window. Shrink from the left until the repeated character is removed before expanding.

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

Tradeoff: Conceptually simpler but the inner while loop means left advances one step at a time — O(n) total but with more iterations than the index-jump approach. Good starting point to explain the concept before optimising.

Gusto-specific tips

Gusto interviewers ask follow-up questions mid-solve — 'what if the character set were only lowercase letters?' (use a 26-element array), 'what about Unicode?' (Map remains correct). The key insight to articulate: when a duplicate is found, the left pointer must jump to max(left, lastSeen[ch] + 1) — the max prevents left from moving backward if the duplicate is outside the window.

Common mistakes

  • Moving left backward — left must only move forward; always take max(left, lastSeen[ch] + 1).
  • Not updating lastSeen after moving left — you must always update the map even when left jumps.
  • Forgetting the empty string case — the loop doesn't execute, maxLen stays 0, which is correct.
  • Using a Set and decrementing right instead of advancing left when a duplicate is found.

Follow-up questions

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

  • Longest Substring with At Most Two Distinct Characters (LC 159).
  • Longest Substring with At Most K Distinct Characters (LC 340).
  • How would your solution change if the input were a stream of characters rather than a string?

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 take max(left, lastSeen[ch] + 1) instead of just lastSeen[ch] + 1?

If the duplicate was seen before the current left boundary, its stored index is stale — we'd move left backward. The max guards against this.

What is the space complexity for ASCII vs Unicode inputs?

For ASCII it's bounded by 128. For full Unicode it's O(n) in the worst case since the map can hold up to n unique characters.

Is the Set approach less efficient?

It's still O(n) amortised — each character is added and removed at most once. But the index-map approach avoids the inner while loop iterations, which is faster in practice.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →