Longest Substring Without Repeating Characters

MediumSliding WindowHash TableStringSliding Window

Problem

You are given a string. Find the length of the longest contiguous stretch of it in which no character repeats.

Example. For "abcabcbb", the longest such stretch is "abc", with length 3.

Key idea

Checking every substring for repeated characters costs O(n²) or worse. A sliding window brings this down to a single pass. Maintain two pointers marking the current window's start and end, and a map from each character to the last index where it appeared. Advance the end pointer one character at a time, growing the window. If the newly added character already appears inside the current window, the window is no longer valid, so pull the start pointer forward to just past that character's earlier occurrence, not further back than where the start pointer already is, since it never needs to move backward. After each step, the window is guaranteed to contain only unique characters, so its length is a candidate for the answer.

Solution

function lengthOfLongestSubstring(s: string): number {
  const lastSeen = new Map<string, number>();
  let start = 0;
  let longest = 0;

  for (let end = 0; end < s.length; end++) {
    const char = s[end];
    const previousIndex = lastSeen.get(char);

    // jump start past the earlier occurrence, but never move it backward
    if (previousIndex !== undefined && previousIndex >= start) {
      start = previousIndex + 1;
    }

    lastSeen.set(char, end);
    longest = Math.max(longest, end - start + 1);
  }

  return longest;
}

Complexity

  • Time: O(n). Each pointer only moves forward, so the two pointers together take at most 2n steps.
  • Space: O(min(n, k)). The map holds at most one entry per distinct character, bounded by the size of the character set.

Watch out for

  • When jumping the start pointer past a repeated character, take the later of its current position and the repeat's recorded index plus one; otherwise the start pointer can incorrectly move backward.
  • Update the last-seen index for every character processed, not only the ones that trigger a repeat.
  • An empty string should report a length of 0.

Pattern

This is the canonical variable-size sliding window: expand the right edge greedily, and contract the left edge only when a validity rule is violated. The same expand/shrink template, swapping in a different validity condition, solves Longest Repeating Character Replacement, Minimum Window Substring, and most other longest- or shortest-substring problems.

Related questions