Skip to main content

3. Longest Substring Without Repeating Characters

mediumAsked at Google

Given a string, return the length of the longest substring with all unique characters. Google asks this to test sliding-window intuition and whether you can articulate why O(n) is achievable when the naive answer is O(n^3).

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Recurring in Google SWE phone-screen reports for L3/L4.
  • Blind (2025-12)— Multiple Google onsite reports list this as a 30-minute medium.

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

Example 2

Input
s = "bbbbb"
Output
1

Example 3

Input
s = "pwwkew"
Output
3

Explanation: The answer is "wke". Note that "pwke" is a subsequence, not a substring.

Approaches

1. Brute-force every substring

Enumerate every (i, j) pair and check whether s[i..j] has duplicates.

Time
O(n^3)
Space
O(min(n, alphabet))
function lengthOfLongestSubstringBrute(s) {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const seen = new Set();
      let ok = true;
      for (let k = i; k <= j; k++) {
        if (seen.has(s[k])) { ok = false; break; }
        seen.add(s[k]);
      }
      if (ok) best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

Tradeoff: Easy to write under pressure but blows up at the upper bound. Name the cost out loud, then move to sliding window.

2. Sliding window with hash map (optimal)

Two pointers (left, right). Expand right; when a duplicate appears, jump left to one past the previous index of the duplicate.

Time
O(n)
Space
O(min(n, alphabet))
function lengthOfLongestSubstring(s) {
  const lastIndex = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastIndex.has(ch) && lastIndex.get(ch) >= left) {
      left = lastIndex.get(ch) + 1;
    }
    lastIndex.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Tradeoff: Single linear pass. The jump-left trick (vs incrementing one at a time) is what makes it true O(n) — left never decreases.

Google-specific tips

Google interviewers want you to articulate the invariant: 'left to right is always a valid window with no duplicates.' If you can state the loop invariant before coding, you score higher. Also, expect a follow-up asking you to return the actual substring, not just its length.

Common mistakes

  • Resetting the window incorrectly: moving left by 1 on each duplicate gives wrong answers; you must jump to one past the prior duplicate index.
  • Forgetting to guard lastIndex.get(ch) >= left — without it, stale indices outside the current window mistrigger the jump.

Follow-up questions

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

  • Return the actual substring, not just its length.
  • What if you could replace up to k characters? (Longest Substring With At Most K Distinct.)
  • What if the input is a stream and you can't store all of it?

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 sliding window O(n) and not O(n^2)?

Both pointers only move forward. left never goes backward, so the total work across all iterations is at most 2n.

What's the trick Google is grading here?

The jump-left optimization. Many candidates write the window correctly but then increment left one at a time on each duplicate — that's still correct but loses the elegant O(n) framing.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →