Sliding Window Pattern

Problem

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

Key Ideas

• Two pointers (left, right) define a window.
• Adjust window to keep all chars unique.
• Set -> shrink one-by-one from left.
• Map -> jump left past last duplicate.

Tests

• "abcabcbb" -> 3 (abc)
• "" -> 0
• "bbbbb" -> 1 (b)
• "abcdefg" -> 7 (all unique)
• "pwwkew" -> 3 (wke)
• "abba" -> 2 (ab / ba)
• "dvdf" -> 3 (vdf)

Set-based, O(n) time / O(min(m, n)) space

Expand right, shrink left until valid.

function lengthOfLongestSubstring(s: string) {
  const window = new Set<string>();
  let left = 0;
  let best = 0;

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

    while (window.has(character)) {
      window.delete(s[left++]);
    }

    window.add(character);

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

  return best;
}

Map-based, O(n) time / O(min(m, n)) space

Track last seen index -> skip left forward in one move.

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

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

    if (window.has(character)) {
      left = Math.max(left, window.get(character)! + 1);
    }

    window.set(character, right);

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

  return best;
}

Variants

• Longest substring with at most k distinct chars.
• Longest substring with exactly k distinct chars.
• Pattern matching substring (freq map).
• Longest subarray sum ≤ target (numeric arrays).
• Smallest substring containing all chars of another string.

Takeaways

• Set -> simpler, but may delete a lot.
• Map -> cleaner jumps, better with clustered duplicates.