How do you find the longest substring without repeating characters?

Picture a train with coaches labelled by letters, and you want the longest run of consecutive coaches where no letter repeats. You hold a frame that you slide along the train. You keep stretching the right edge of the frame to include the next coach. The moment a letter appears twice inside the frame, you pull the left edge forward just past the earlier copy of that letter, so the frame is valid again. Along the way, you note the widest the frame ever got.

You never go back and restart from scratch. Each coach enters the frame once and leaves at most once. That is why it is fast.

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map(); // character -> last index where it appeared
  let left = 0; // start of the current window
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    // If ch was seen inside the current window, jump left past it
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1;
    }
    lastSeen.set(ch, right); // update the latest position of ch
    best = Math.max(best, right - left + 1); // window is s[left..right]
  }
  return best;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3
console.log(lengthOfLongestSubstring("bbbbb")); // Output: 1
console.log(lengthOfLongestSubstring("pwwkew")); // Output: 3
console.log(lengthOfLongestSubstring("abba")); // Output: 2
console.log(lengthOfLongestSubstring("")); // Output: 0
console.log(lengthOfLongestSubstring("dvdf")); // Output: 3

Trace for "pwwkew":

The answer is 3 ("wke" or "kew"). Note "pwke" is a subsequence, not a substring, so it does not count.

• The window s[left..right] always contains distinct characters. That is the invariant.
• When a repeat arrives, all positions up to and including its previous copy can never be part of a valid window ending at right, so left jumps straight past it.
• The check lastSeen.get(ch) >= left matters. Look at "abba": when the second a arrives at index 3, left is already 2 (it moved past the first b). The old a at index 0 is outside the window, so left must not move back to 1. Without this check the answer would wrongly be 3.

Approaches, from slow to fast:

1. Brute force: check every substring and test if its characters are unique. O(n³), or O(n²) with a set.
2. Sliding window with a set: move left forward one step at a time, removing characters, until the repeat is gone. O(n), each character added and removed at most once.
3. Sliding window with last-seen indexes (above): left jumps directly. Still O(n), with fewer steps.

k is the number of distinct characters possible, at most the size of the alphabet (for example 128 for ASCII), so the space is often described as O(min(n, k)).

• Letting left move backwards, as in the "abba" case. Either check that the old index is inside the window, or write left = Math.max(left, lastSeen.get(ch) + 1).
• Off-by-one on the length. The window from left to right inclusive has right - left + 1 characters.
• Confusing substring (contiguous) with subsequence (any order-preserving pick).
• Restarting the scan from left each time a repeat is found, which turns the solution back into O(n²).

• How would you return the substring itself, not just its length?
• What is the longest substring with at most k distinct characters?
• How do you find the smallest window that contains all characters of another string?
• Why is the sliding window O(n) when there is a loop inside a loop in the set version?