Skip to main content

15. Longest Substring Without Repeating Characters

mediumAsked at SoFi

Find the length of the longest substring with all unique characters — SoFi uses this to test sliding-window mechanics that show up in time-window risk scoring.

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

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
"abcabcbb"
Output
3

Example 2

Input
"bbbbb"
Output
1

Approaches

1. Brute force

Check every substring with a set for uniqueness.

Time
O(n^3)
Space
O(min(n, alphabet))
function lengthOfLongestSubstring(s) {
  let best = 0;
  for (let i = 0; i < s.length; i++)
    for (let j = i; j < s.length; j++) {
      const sub = s.slice(i, j+1);
      if (new Set(sub).size === sub.length) best = Math.max(best, sub.length);
    }
  return best;
}

Tradeoff:

2. Sliding window with map

Maintain a window [left, right] and a map of last-seen index per char. On collision, jump left past the previous occurrence.

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

Tradeoff:

SoFi-specific tips

SoFi uses sliding-window patterns extensively in fraud and risk scoring (rolling 30-day spend windows, rolling NAV calculations for portfolios) — mention the analogy and you'll get bonus signal.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →