Longest Substring Without Repeating Characters

Examples

Input: s = "abcabcbb"
Output: 3

The longest run with no repeats is "abc", which has length 3.

Input: s = "bbbbb"
Output: 1

Every character repeats immediately, so the best you can do is a single character, "b".

Input: s = "pwwkew"
Output: 3

"wke" is the longest substring without repeats. Note "pwke" is not a valid answer because it is not contiguous in the original string.

Constraints

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

• s consists of English letters, digits, symbols, and spaces.

Approach

A brute-force approach would check every possible substring, and for each one scan it to see if it has repeated characters. That's a lot of redundant scanning since substrings overlap heavily.

Instead, use a sliding window: keep two pointers, left and right, marking the current substring, plus a set of the characters currently inside that window. Move right forward one step at a time, adding characters to the set. If the character you're adding is already in the set, that means the window has a duplicate — so shrink the window from the left, removing characters, until the duplicate is gone. At every step, the window is duplicate-free, so its length is a candidate answer. This way each character is added and removed from the window at most once, giving a single pass overall.

Solutions

Brute Force — Check Every Substring

Try every start and end position, and for each candidate substring scan it to check whether all characters are unique. Simple, but re-scans overlapping substrings many times.

function lengthOfLongestSubstring(s) {
  let best = 0;

  for (let start = 0; start < s.length; start++) {
    const seen = new Set();
    for (let end = start; end < s.length; end++) {
      if (seen.has(s[end])) {
        break;
      }
      seen.add(s[end]);
      best = Math.max(best, end - start + 1);
    }
  }

  return best;
}

Time: O(n²) · Space: O(min(n, alphabet size))

Optimal — Sliding Window with a Set

Grow the window by moving the right edge forward. Whenever the incoming character is already inside the window, shrink from the left until it isn't a duplicate anymore, then keep going.

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

  for (let right = 0; right < s.length; right++) {
    while (window.has(s[right])) {
      window.delete(s[left]);
      left++;
    }
    window.add(s[right]);
    best = Math.max(best, right - left + 1);
  }

  return best;
}

Time: O(n) · Space: O(min(n, alphabet size))