3. Longest Substring Without Repeating Characters

mediumAsked at Duolingo

Find the longest contiguous substring with all unique characters — the sliding-window pattern Duolingo applies when scanning a learner's typed sentence for the longest unique-token run to validate a free-form translation exercise.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Given a string s, find the length of the longest substring that contains no 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

Explanation: The answer is 'abc', with length 3.

Example 2

Input

s = "bbbbb"

Output

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

Example 3

Input

s = "pwwkew"

Output

Explanation: 'wke' has length 3.

Approaches

1. Brute force — check all substrings

Enumerate every substring and check whether it has all unique characters using a Set.

Time: O(n^3)
Space: O(min(n, m))

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:

2. Optimal — sliding window with last-index map

Maintain a window [left, right]; when a repeat is found, jump left past the previous occurrence using a stored index map — single pass.

Time: O(n)
Space: O(min(n, m))

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

Tradeoff:

Duolingo-specific tips

Duolingo interviewers specifically look for the jump-left optimization: instead of moving left one step at a time, you skip directly past the duplicate. This mirrors how the product's text-diffing logic works — you don't re-scan validated characters. Articulate the invariant: 'left is always positioned so that s[left..right] is a valid unique window.' Expect a follow-up: 'What if the string contains Unicode characters?' — answer: Map keys handle multi-byte code points correctly, but a fixed-size array would not.

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

Practice these live with InterviewChamp.AI →