Skip to main content

18. Longest Substring Without Repeating Characters

mediumAsked at PayPal

Find the length of the longest substring with all unique characters. PayPal uses this classic sliding-window problem to evaluate candidates' ability to maintain a dynamic window — directly analogous to deduplication windows in real-time transaction stream processing.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Glassdoor (2026)— PayPal SWE L3 reported sliding-window string problem in technical phone screen
  • LeetCode Discuss (2025)— Multiple PayPal OA reports include LC 3 as the primary medium-difficulty question

Problem

Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous sequence of characters within the string.

Constraints

  • 0 <= s.length <= 50000
  • 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

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

Approaches

1. Brute force (check all substrings)

Generate all O(n^2) substrings and check each for uniqueness using a Set.

Time
O(n^3)
Space
O(min(n, charset))
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) or O(n^3) depending on inner Set operations — too slow for 50k input; always pivot to sliding window.

2. Sliding window with last-seen index map

Maintain a window [left, right] of unique characters. When a duplicate is found at right, jump left past the previous occurrence of that character using a stored index map — no backtracking needed. This gives O(n) with a single scan.

Time
O(n)
Space
O(min(n, charset))
function lengthOfLongestSubstring(s) {
  const lastIndex = new Map(); // char -> most recent index
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    // If char is inside the current window, shrink from the left
    if (lastIndex.has(ch) && lastIndex.get(ch) >= left) {
      left = lastIndex.get(ch) + 1;
    }
    lastIndex.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

Tradeoff: The `>= left` guard is critical — it prevents jumping left backwards when a character was seen before the current window started. At PayPal, explain this as a bounded deduplication window over a stream.

PayPal-specific tips

PayPal interviews focus on payment processing, fraud detection logic, financial reconciliation algorithms, and distributed transaction design. Hash maps, sliding windows, and two-pointer techniques appear frequently.

Common mistakes

  • Moving left to lastIndex.get(ch) instead of lastIndex.get(ch) + 1, leaving the duplicate inside the window
  • Not checking that the stored index is within the current window (>= left), causing left to move backwards
  • Using a Set and shrinking left one step at a time instead of jumping directly — correct but O(n^2) worst case

Follow-up questions

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

  • Find the actual longest substring, not just its length
  • Allow at most k repeating characters — LC 340 (Longest Substring with At Most K Distinct Characters)
  • Solve for a stream of characters arriving one at a time — how do you maintain the window efficiently?

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 store last index instead of using a Set?

A Set-based approach requires shrinking the window one character at a time when a duplicate appears, costing O(n) per step in the worst case. Storing last index lets you jump directly to the correct left boundary in O(1).

Does this work for Unicode characters?

Yes — a Map keyed by character string works for any Unicode code point. For ASCII-only inputs you can use a 128-slot array for marginally better cache performance.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →