Template library

/**
 * Sliding window (variable length), longest valid window.
 * Expand `right`, shrink `left` while the invariant breaks, then record the answer.
 *
 * Minimum covering window: shrink while still valid, update `best` only when valid
 * (often start with `best = Infinity`).
 */
function slidingWindow(s: string): number {
  const freq = new Map<string, number>();
  let left = 0;
  let best = 0;

  const windowOk = () => {
    // Replace with the problem invariant (e.g. all unique, sum ≤ k).
    return true;
  };

  for (let right = 0; right < s.length; right++) {
    // 1) expand: add s[right] into window state
    const add = s[right]!;
    freq.set(add, (freq.get(add) ?? 0) + 1);

    // 2) shrink while the invariant is broken
    while (left <= right && !windowOk()) {
      const rem = s[left]!;
      const next = (freq.get(rem) ?? 0) - 1;
      if (next <= 0) freq.delete(rem);
      else freq.set(rem, next);
      left++;
    }

    // 3) window [left, right] is valid, update answer
    best = Math.max(best, right - left + 1);
  }

  return best;
}

export { slidingWindow };

/** Two pointers template: sorted two-sum (1-based indices). */
export function twoSumSorted(numbers: number[], target: number): number[] {
  let lo = 0, hi = numbers.length - 1;
  while (lo < hi) {
    const sum = numbers[lo]! + numbers[hi]!;
    if (sum === target) return [lo + 1, hi + 1];
    if (sum < target) lo++;
    else hi--;
  }
  throw new Error("No solution");
}

/** Fast/slow template: detect cycle (Floyd). */
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
export function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast?.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

/** Binary search template: lower-bound, then exact match. */
export function binarySearch(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}