Skip to main content

13. Longest Substring Without Repeating Characters

mediumAsked at Klarna

Find the length of the longest substring with all distinct characters.

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

Example 2

Input
s = "bbbbb"
Output
1

Approaches

1. Brute-force all substrings

Try every substring and verify uniqueness with a set.

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

Tradeoff:

2. Sliding window with last-seen map

Slide a right pointer through the string, jumping the left pointer past the last occurrence of the current char. Each character is visited at most twice.

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

Tradeoff:

Klarna-specific tips

Klarna's risk-feature engineers reuse this sliding-window shape on session-event streams, so they grade your boundary handling more strictly than the absolute best length.

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 Klarna interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →