Longest Substring Without Repeating Characters

Try It Yourself

Use the editor below to maintain a contiguous window containing no duplicate characters. Expand from the right and shrink from the left only when the new character is already present.

Submit your implementation when it passes the examples. Empty strings, spaces, and repetitions after a gap should all behave correctly.

Longest Substring Without Repeating Characters

mediumSliding Window · Strings · Hash Set30 minLC 3

Problem

Given a string s, return the length of its longest contiguous substring with no repeated characters.

The substring must use adjacent characters from the original string.

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The longest substring is "abc".

Example 2:

Input: s = "bbbbb"

Output: 1

Constraints

0 ≤ s.length ≤ 50,000
s may contain letters, digits, spaces, and symbols.

0 attempts

Solution

A set represents the characters currently inside the window. When the right character is already in the set, remove characters from the left until that duplicate is gone.

Add the new character and update the longest valid window length after every expansion.

function lengthOfLongestSubstring(s) {
  const window = new Set();
  let left = 0;
  let longest = 0;

  for (let right = 0; right < s.length; right++) {
    while (window.has(s[right])) {
      window.delete(s[left]);
      left++;
    }

    window.add(s[right]);
    longest = Math.max(longest, right - left + 1);
  }

  return longest;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	Each character enters and leaves the window at most once.
Auxiliary space	`O(k)`	The set stores at most k characters from the current window.