Permutation in String

Difficulty: Medium

You're given two strings, s1 and s2. Check whether s2 contains a permutation of s1 as a contiguous substring — in other words, whether some contiguous run of s2 uses exactly the same letters, with exactly the same counts, as s1, just possibly in a different order.

Return true if such a substring exists, and false otherwise.

Examples

Input: s1 = "ab", s2 = "eidbaooo"
Output: true

"ba" is a substring of s2, and it is a rearrangement of "ab".

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

No contiguous substring of s2 has exactly one "a" and one "b".

Input: s1 = "adc", s2 = "dcda"
Output: true

"dca" (positions 0-2 of s2) uses the same letters as "adc".

Constraints

1 <= s1.length, s2.length <= 10^4
s1 and s2 consist of lowercase English letters.

Approach

Since a permutation just rearranges the same letters, this problem is really: does s2 contain any contiguous window, the same length as s1, whose letter counts exactly match s1's letter counts?

The brute-force approach checks every window of that fixed length by building a fresh count of its letters and comparing it to s1's counts — that recomputation is wasteful since neighboring windows overlap almost entirely.

A sliding window fixes this: build the letter counts for s1 once, and for the first window of s2. Then slide the window one step at a time — each slide removes exactly one letter (the one falling off the left) and adds exactly one letter (the one entering on the right), so the counts can be updated incrementally instead of recomputed. After each slide, compare the window's counts to s1's counts; if they ever match exactly, a valid permutation has been found.

Solutions

Brute Force — Recount Every Window

For every possible window of s2 with the same length as s1, build its letter counts from scratch and compare them against s1's counts.

function checkInclusion(s1, s2) {
  const need = buildCounts(s1);
  const windowSize = s1.length;

  for (let start = 0; start + windowSize <= s2.length; start++) {
    const have = buildCounts(s2.slice(start, start + windowSize));
    if (sameCounts(need, have)) {
      return true;
    }
  }

  return false;
}

function buildCounts(str) {
  const counts = {};
  for (const ch of str) {
    counts[ch] = (counts[ch] || 0) + 1;
  }
  return counts;
}

function sameCounts(a, b) {
  const keys = new Set([...Object.keys(a), ...Object.keys(b)]);
  for (const key of keys) {
    if ((a[key] || 0) !== (b[key] || 0)) {
      return false;
    }
  }
  return true;
}

Time: O(n * m) — n windows, each costing O(m) to build and compare, m = s1.length · Space: O(26) per window — constant, one count per lowercase letter

Optimal — Fixed-Size Sliding Window

Keep one running count array for the current window in s2, updated incrementally as the window slides by one position at a time, and compare it to s1's counts after each slide.

function checkInclusion(s1, s2) {
  if (s1.length > s2.length) return false;

  const need = new Array(26).fill(0);
  const have = new Array(26).fill(0);
  const base = "a".charCodeAt(0);

  for (let i = 0; i < s1.length; i++) {
    need[s1.charCodeAt(i) - base]++;
    have[s2.charCodeAt(i) - base]++;
  }

  if (matches(need, have)) return true;

  for (let right = s1.length; right < s2.length; right++) {
    have[s2.charCodeAt(right) - base]++;
    const left = right - s1.length;
    have[s2.charCodeAt(left) - base]--;

    if (matches(need, have)) return true;
  }

  return false;
}

function matches(a, b) {
  for (let i = 0; i < 26; i++) {
    if (a[i] !== b[i]) return false;
  }
  return true;
}

Time: O(n + m) — n = s2.length, m = s1.length, since the letter comparison is a constant 26 slots · Space: O(26) — constant, two fixed-size count arrays