Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumsliding-window

Longest Substring Without Repeating Characters

Problem (restated)

Given a string s, return the length of the longest substring that contains no repeating characters.

Intuition

The answer is a contiguous range → sliding window. Expand right; when a duplicate appears inside the window, advance left past the previous occurrence.

Approaches

Sliding window + last-seen index

Tested only

Time O(n)Space O(min(n, Σ))

Idea. Maintain window [left,right] with unique chars. Map char→last index. On duplicate in window, set left = max(left, lastIndex+1). Track max length.

Walkthrough. s=“abcabcbb”. Windows grow “a”,“ab”,“abc”, then second a forces left past first a → “bca”, … best=3.

Trade-offs. Linear time optimal. last-seen map is simpler than a frequency map for this problem.

Solution

export function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right]!;
    if (last.has(ch) && last.get(ch)! >= left) {
      left = last.get(ch)! + 1;
    }
    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

export function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right]!;
    if (last.has(ch) && last.get(ch)! >= left) {
      left = last.get(ch)! + 1;
    }
    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Check all substrings

Tested only

Time O(n²)Space O(min(n, Σ))

Idea. For each start index, extend while chars are unique using a set.

Walkthrough. From each i expand until a repeat; track max length.

Trade-offs. Simple but quadratic. use only as a reference implementation.

Solution

export function lengthBrute(s: string): number {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    const seen = new Set<string>();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j]!)) break;
      seen.add(s[j]!);
      best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

export function lengthBrute(s: string): number {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    const seen = new Set<string>();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j]!)) break;
      seen.add(s[j]!);
      best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

Template connection

Max-window form of the Sliding Window template: shrink while the window is invalid (duplicate present).

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What input would break a careless off-by-one in your window/pointer logic?