Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumsliding-window

Permutation in String

Problem (restated)

Return true if s2 contains a permutation of s1 as a contiguous substring.

Intuition

A permutation of s1 is any window of length |s1| with the same character counts.

Approaches

Fixed window frequency match

Unverified

Time O(n)Space O(1)

Idea. Count s1 frequencies. Slide a window of that length over s2, compare counts (or maintain a matches counter).

Walkthrough. s1=“ab”, s2=“eidbaooo”. Window “ba” matches counts of a,b → true.

Trade-offs. O(1) alphabet space for lowercase English. Sorting every window is slower.

Solution

export function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) return false;
  const need = new Array<number>(26).fill(0);
  const win = new Array<number>(26).fill(0);
  for (let i = 0; i < s1.length; i++) {
    need[s1.charCodeAt(i)! - 97]!++;
    win[s2.charCodeAt(i)! - 97]!++;
  }
  const eq = () => need.every((v, i) => v === win[i]);
  if (eq()) return true;
  for (let i = s1.length; i < s2.length; i++) {
    win[s2.charCodeAt(i)! - 97]!++;
    win[s2.charCodeAt(i - s1.length)! - 97]!--;
    if (eq()) return true;
  }
  return false;
}

export function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) return false;
  const need = new Array<number>(26).fill(0);
  const win = new Array<number>(26).fill(0);
  for (let i = 0; i < s1.length; i++) {
    need[s1.charCodeAt(i)! - 97]!++;
    win[s2.charCodeAt(i)! - 97]!++;
  }
  const eq = () => need.every((v, i) => v === win[i]);
  if (eq()) return true;
  for (let i = s1.length; i < s2.length; i++) {
    win[s2.charCodeAt(i)! - 97]!++;
    win[s2.charCodeAt(i - s1.length)! - 97]!--;
    if (eq()) return true;
  }
  return false;
}

Template connection

Fixed-length sliding window whose counts match s1 (anagram / permutation check).

Reflection

A window fixed at s1.length is how you hear “permutation”. Need/have counts, or a 26-wide difference?
When the window slides, forgetting to put back the character that left produces which false positive?
If s1 is longer than s2, do you return false immediately?