567. Permutation in String

Given strings s1 and s2 of lowercase letters, return true if s2 contains a permutation of s1 as a contiguous substring.

Keep letter counts for s1 and for the current window, plus how many of the 26 letters have equal counts. Sliding the window changes two letters; when all 26 match, the window is a permutation.

1function checkInclusion(s1: string, s2: string): boolean {
2  if (s1.length > s2.length) return false;
3  const a = new Array(26).fill(0), b = new Array(26).fill(0), idx = (c: string) => c.charCodeAt(0) - 97;
4  for (let i = 0; i < s1.length; i++) { a[idx(s1[i])]++; b[idx(s2[i])]++; }
5  let matches = 0;
6  for (let k = 0; k < 26; k++) if (a[k] === b[k]) matches++;
7  for (let r = s1.length; r < s2.length; r++) {
8    if (matches === 26) return true;
9    const add = idx(s2[r]), drop = idx(s2[r - s1.length]);
10    b[add]++; if (b[add] === a[add]) matches++; else if (b[add] === a[add] + 1) matches--;
11    b[drop]--; if (b[drop] === a[drop]) matches++; else if (b[drop] === a[drop] - 1) matches--;
12  }
13  return matches === 26;
14}

matches = 0

s2

need (s1)

window

Count s1 and the first window "ei".

1 / 0

Space: play/pause · ←/→: step