Longest Substring Without Repeating Characters

Intuition

We’re looking for the longest window of characters with no repeats.

Expand the window to the right; if we see a duplicate, jump the left edge just past the previous occurrence so the window remains duplicate-free.

Approach

• Keep two pointers: left (start of window) and right (current char).
• Maintain lastSeen[char] = last index of char.
• For each right:
  • If char was seen at index j ≥ left, move left = j + 1 to exclude the previous occurrence.
  • Update lastSeen[char] = right.
  • Update best = max(best, right - left + 1). This ensures the window s[left..right] always has unique chars.

Proof of Correctness

Invariant: The current window s[left..right] contains no duplicates.

• Initially true (empty window).
• When we encounter a duplicate of char last seen at j, moving left to j+1 removes the duplicate and preserves all other characters, restoring the invariant.
• We consider every index once as right advances monotonically; left never moves backward.
• The maximum window size observed is the answer, since any valid substring is considered as a window at some step.

Complexity

• Time:
  • Each index enters and leaves the window at most once.
  • Total: 0(n).
• Space:
  • Map holds at most one entry per distinct character (Σ = alphabet size).
  • Total: 0(min(n,Σ)).

Code

export function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>();
  let best = 0;
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];

    if (last.has(ch) && (last.get(ch) as number) >= left) {
      left = (last.get(ch) as number) + 1;
    }

    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }

  return best;
}

def lengthOfLongestSubstring(s: str) -> int:
    last = {}
    best = 0
    left = 0

    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)

    return best