Longest Substring Without Repeating Characters

Problem

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

Intuition

Use a sliding window with two pointers. Expand the right pointer to include new characters. When a duplicate is found, shrink the window from the left until the duplicate is removed. A Set tracks which characters are currently in the window.

Solution

function lengthOfLongestSubstring(s: string): number {
  const seen = new Set<string>();
  let left = 0;
  let maxLen = 0;
 
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
 
  return maxLen;
}

Optimized with Map

We can skip directly to the position after the duplicate instead of shrinking one by one:

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

Complexity

• Time: O(n) — each character is visited at most twice (Set version) or once (Map version)
• Space: O(min(n, m)) — where m is the character set size

Key Takeaway

The sliding window pattern is ideal for substring/subarray problems with a constraint. Expand right, shrink left when the constraint is violated, track the best window seen.