Skip to main content

12. Longest Substring Without Repeating Characters

mediumAsked at Revolut

Find the length of the longest substring of unique characters via a sliding window, a Revolut bread-and-butter screen for streaming transaction-ID windows.

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

Problem

Given a string s, find the length of the longest substring without repeating characters. The window must be contiguous.

Constraints

  • 0 <= s.length <= 5 * 10^4
  • ASCII printable characters

Examples

Example 1

Input
s="abcabcbb"
Output
3

Example 2

Input
s="bbbbb"
Output
1

Approaches

1. All substrings

Enumerate every substring and test uniqueness with a set.

Time
O(n^3)
Space
O(n)
for i in 0..n: for j in i+1..n: if unique(s.slice(i,j)) best = max(best,j-i);

Tradeoff:

2. Sliding window with map

Move right edge, remember last index of each char, jump left edge past any repeat. Linear time.

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

Tradeoff:

Revolut-specific tips

Revolut frames this as deduping a stream of idempotency keys within a sliding settlement window — explicitly name the left-edge jump as the dedup-clear step.

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

Practice these live with InterviewChamp.AI →