longest-substring-without-repeating.ts

/**
 * 3. Longest Substring Without Repeating Characters  (Medium)
 * Link: https://leetcode.com/problems/longest-substring-without-repeating-characters/
 *
 * Given a string `s`, return the length of the longest substring that contains
 * no repeating characters.
 *
 * Example:
 *   Input:  s = "abcabcbb"
 *   Output: 3            // "abc"
 *
 * Approach:
 *   Sliding window with a map of each character's last seen index. Expand the
 *   right edge; when we hit a character already inside the window, jump the left
 *   edge to just past its previous occurrence. Track the best window length.
 *
 * Time:  O(n)  — each character processed once.
 * Space: O(k)  — k = size of the character set in the window.
 */
export function lengthOfLongestSubstring(s: string): number {
  const lastSeen = new Map<string, number>();
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    const prev = lastSeen.get(ch);
    if (prev !== undefined && prev >= left) {
      left = prev + 1;
    }
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }

  return best;
}