Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Sliding Window

Guide 5 of 6 · Path 5 of 6

← PreviousNext →

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

Tested only
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;
}

Reflection