567. Permutation in String☆

function longestOnes(nums: number[], k: number): number {
  let L = 0;
  let zeros = 0;
  let best = 0;

  for (let R = 0; R < nums.length; R++) {
    if (nums[R] === 0) zeros++;       // a 0 entered the window

    while (zeros > k) {               // too many 0s to flip
      if (nums[L] === 0) zeros--;     // a 0 is leaving on the left
      L++;
    }

    best = Math.max(best, R - L + 1); // window now has <= k zeros
  }

  return best;
}

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // stores INDICES; values decreasing front→back

  for (let i = 0; i < nums.length; i++) {
    // 1 · evict the front if it has slid out of the window
    if (deque.length && deque[0] <= i - k) {
      deque.shift();
    }
    // 2 · drain the back of all values ≤ the incoming value
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    // 3 · push the current index
    deque.push(i);
    // 4 · record the max once the first window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  return result;
}

function checkInclusion(s1: string, s2: string): boolean {
  const k = s1.length;
  if (k > s2.length) return false;

  // Frequency arrays for s1 (need) and the current window of s2 (have)
  const need = new Array<number>(26).fill(0);
  const have = new Array<number>(26).fill(0);
  const a = 'a'.charCodeAt(0);

  for (const c of s1) need[c.charCodeAt(0) - a]++;

  // matches = number of letters whose count in 'have' equals 'need'
  let matches = 0;

  // Seed the first window
  for (let i = 0; i < k; i++) {
    const idx = s2.charCodeAt(i) - a;
    have[idx]++;
    if (have[idx] === need[idx]) matches++;
    else if (have[idx] - 1 === need[idx]) matches--;
  }
  if (matches === 26) return true;

  // Slide one step at a time
  for (let r = k; r < s2.length; r++) {
    // Bring the right character into the window
    const rIdx = s2.charCodeAt(r) - a;
    have[rIdx]++;
    if (have[rIdx] === need[rIdx]) matches++;
    else if (have[rIdx] - 1 === need[rIdx]) matches--;

    // Evict the leftmost character
    const lIdx = s2.charCodeAt(r - k) - a;
    have[lIdx]--;
    if (have[lIdx] === need[lIdx]) matches++;
    else if (have[lIdx] + 1 === need[lIdx]) matches--;

    if (matches === 26) return true;
  }
  return false;
}

function minWindow(s: string, t: string): string {
  if (t.length === 0) return '';

  // Build the "need" map: how many of each t-char we require
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  const required = need.size; // distinct chars we must satisfy

  const window = new Map<string, number>(); // current window counts
  let have = 0;   // distinct chars currently satisfied
  let L = 0;

  let bestLen = Infinity;
  let bestL = 0, bestR = 0;

  for (let R = 0; R < s.length; R++) {
    // 1. Expand: add s[R] to the window
    const c = s[R];
    window.set(c, (window.get(c) ?? 0) + 1);
    if (need.has(c) && window.get(c) === need.get(c)) {
      have++; // this char's count just hit its requirement
    }

    // 2. Contract: shrink from the left while window is valid
    while (have === required) {
      const len = R - L + 1;
      if (len < bestLen) { bestLen = len; bestL = L; bestR = R; }

      const lc = s[L];
      window.set(lc, window.get(lc)! - 1);
      if (need.has(lc) && window.get(lc)! < need.get(lc)!) {
        have--; // we dropped below requirement; window invalid
      }
      L++;
    }
  }

  return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);
}