Longest Substring Without Repeating CharactersMedium

Given a string, find the length of the longest substring without repeating characters.

Examples

Input: s = "abcabcbb" → Output: 3 ("abc")

Input: s = "pwwkew" → Output: 3 ("wke")

Approach

Checking every substring for repeats is O(n²) (or worse). A sliding window fixes it: expand the window one character at a time, and track the last-seen index of every character. The moment you hit a character already inside the current window, jump the window's LEFT edge to just past that character's previous occurrence — no need to shrink one step at a time, jump straight there.

Complexity — best & worst case

Brute force — time O(n²)

Optimal — time O(n) worst case (all unique, window only grows), O(1) best case (immediate repeat, e.g. "aa")

Optimal — space O(min(n, alphabet size))

Code

// Given a string, find the length of the longest substring without
// repeating characters.

// --- Brute force: check every substring ---
function longestUniqueBrute(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;
}

// --- Optimal: sliding window, shrink from the left when a repeat shows up ---
function longestUnique(s) {
  const seen = new Map(); // char -> last index seen
  let left = 0;
  let max = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    if (seen.has(char) && seen.get(char) >= left) {
      left = seen.get(char) + 1; // jump the window past the repeat
    }
    seen.set(char, right);
    max = Math.max(max, right - left + 1);
  }
  return max;
}

// --- Example Usage ---
console.log(longestUnique("abcabcbb")); // 3 ("abc")
console.log(longestUniqueBrute("abcabcbb")); // 3
console.log(longestUnique("bbbbb")); // 1
console.log(longestUnique("pwwkew")); // 3 ("wke")