Permutation in String

SLIDING WINDOW · MEDIUM

The problem

You’re given two strings, s1 and s2. Decide whether s2 contains a contiguous block of characters that is SOME rearrangement of s1 — exactly the same multiset of characters as s1, in any order, but packed together with no gaps and no skipped characters. In other words: does any window of s2, exactly s1.length characters long, use precisely the same letters (and letter counts) as s1?

For example s1="ab", s2="eidbaooo" returns true — the substring "ba" is a rearrangement of "ab" and sits right there at index 3. But s1="ab", s2="eidboaoo" returns false — "a" and "b" both appear in s2, but never adjacent to each other as a two-character block, so no contiguous substring ever matches. Order inside the matching window doesn’t matter at all — only which characters (and how many of each) are in it.

Solution 1: Brute force — generate every permutation of s1, test each against s2

The most literal reading of the problem: actually build the set of every distinct rearrangement of s1 (de-duplicated — if s1 has repeated characters, swapping two identical letters doesn’t produce a genuinely different string), then check each one with s2.includes(candidate). The first candidate that’s found is the answer. This is a completely real, correct algorithm — but the number of distinct permutations of a k-character string is k! in the worst case, and each .includes() check itself costs up to O(k) against an O(n)-long haystack. 7! is already 5,040 candidate strings; 10! is 3.6 million. This demo is deliberately capped at s1.length = 3 — anything much bigger stops being animatable at all, which is exactly the point: this approach is a correct answer to a toy-sized version of the problem, not a practical one.

s1 = "abc", s2 = "eidcabooo" — 7 steps total

Press play to run the brute force algorithm.

Step 0 / 7

The code

function checkInclusionBruteForce(s1, s2) {
  const perms = permutationsOf(s1); // every DISTINCT rearrangement of s1
  for (const p of perms) {
    if (s2.includes(p)) return true;
  }
  return false;
}

function permutationsOf(s) {
  const results = new Set(); // Set dedupes identical strings from repeated chars
  function backtrack(path, remaining) {
    if (remaining.length === 0) {
      results.add(path.join(''));
      return;
    }
    const seenAtThisLevel = new Set();
    for (let i = 0; i < remaining.length; i++) {
      const c = remaining[i];
      if (seenAtThisLevel.has(c)) continue; // skip a repeated char at this depth
      seenAtThisLevel.add(c);
      path.push(c);
      backtrack(path, remaining.slice(0, i).concat(remaining.slice(i + 1)));
      path.pop();
    }
  }
  backtrack([], s.split(''));
  return Array.from(results);
}

Line by line:

permutationsOf(s1) does the actual generation work — a standard backtracking permutation builder, collected into a Set so identical strings produced from swapping equal characters (e.g. two as in "aab") collapse into one entry instead of counting as separate permutations.
seenAtThisLevel is the dedupe trick itself: at each recursive depth, if the same character value has already been tried as the next pick, skip it — this prunes duplicate branches during generation rather than generating them all and filtering afterward, but the asymptotic cost is still driven by k! in the worst case (all-distinct characters).
checkInclusionBruteForce itself is trivial once the permutation list exists: loop through every candidate and call s2.includes(p), returning the instant one is found.
s2.includes(p) is not free — a naive substring search costs O(k·n) in the worst case (V8’s real implementation is more optimized in practice, but the honest worst-case bound is what the complexity table below reports).

Complexity

Time	Space	Approach
O(k! · k · n)	O(k! · k)	Generate every distinct permutation of s1, test each with .includes()

Solution 2: Optimal — fixed-size sliding window with frequency-count matching

The brute force’s real waste is regenerating and re-testing whole strings from scratch. A permutation match doesn’t care about ORDER at all — only about which characters, and how many of each, sit inside some window of s2 exactly s1.length characters wide. That reframes the problem entirely: build a frequency map (need) of s1’s characters, then slide a window of exactly that fixed width across s2, maintaining a running frequency map of whatever is currently inside the window. The window is a permutation of s1 the moment its frequency map matches need exactly.

Checking “does the whole window’s frequency map match need” from scratch on every slide would cost O(k) per slide — back to O(n·k) overall. The optimization is a running matches counter: it tracks how many DISTINCT characters currently have their count in the window exactly equal to their required count in need. A window is a full match exactly when matches === need.size (every required character’s count is satisfied — not more, not less). Sliding the window by one position only ever changes TWO characters’ counts: the new character entering on the right, and the old character leaving on the left. So each slide only needs to re-check those two characters’ match status — an O(1) update, not a full window rescan.

s1 = "ab", s2 = "eidbaooo" — sliding window matches found at index 3

Press play to run the optimal algorithm.

Step 0 / 6

The code

function checkInclusionOptimal(s1, s2) {
  const k = s1.length;
  if (k > s2.length) return false;

  const need = new Map();
  for (const c of s1) need.set(c, (need.get(c) || 0) + 1);

  const window = new Map();
  let matches = 0;

  function bump(c, delta) {
    const before = window.get(c) || 0;
    const after = before + delta;
    if (after === 0) window.delete(c); else window.set(c, after);
    const wasMatch = need.has(c) && before === need.get(c);
    const isMatch = need.has(c) && after === need.get(c);
    if (wasMatch && !isMatch) matches--;
    if (!wasMatch && isMatch) matches++;
  }

  for (let i = 0; i < k; i++) bump(s2[i], 1); // fill the first window
  if (matches === need.size) return true;

  for (let right = k; right < s2.length; right++) {
    bump(s2[right], 1);          // char entering on the right
    bump(s2[right - k], -1);     // char leaving on the left
    if (matches === need.size) return true;
  }

  return false;
}

Line by line:

need is a frequency map of s1 — how many of each character the window has to contain to be a permutation.
bump(c, delta) is the entire O(1) trick: it adjusts one character’s count by +1 or -1, and compares that ONE character’s count before and after against need. If the count just transitioned INTO exact equality with need, matches goes up; if it just transitioned OUT of equality, matches goes down. Every other character’s count and match status is completely untouched.
The first loop fills the initial window (s2[0..k-1]) one character at a time, using the same bump helper — no separate code path for “building” vs “sliding”.
The sliding loop is exactly two bump calls per iteration: add s2[right] (the new right edge), remove s2[right - k] (whatever just fell off the left edge of the fixed-width window). That’s the entire slide — nothing else in window or matches is recomputed.
matches === need.size is the win condition — need.size is the number of DISTINCT characters in s1 (a Map’s key count), not s1.length. Every distinct required character having its exact count satisfied is precisely what “the window is a permutation of s1” means.

Complexity

Time	Space	Approach
O(n)	O(1)	Fixed-size sliding window, incremental frequency-count matching (matches counter)

Complexity comparison

Solution	Time	Space
Brute force (generate + test permutations)	O(k! · k · n)	O(k! · k)
Optimal (fixed sliding window)	O(n)	O(1)

This is a genuinely dramatic gap, and it’s honest to call it one: factorial time in k = s1.length versus linear time in n = s2.length, with the space dropping from “grows faster than exponentially” down to a constant bounded by the alphabet (at most 26 distinct lowercase letters, or however many distinct characters actually appear). Unlike some brute-force/optimal pairs on this site where the honest story is “same time, better space” or vice versa, here BOTH time and space genuinely improve, and by an enormous margin.

Interview corner

Why does this problem use a FIXED-size sliding window instead of the grow/shrink variable-size window used in problems like Minimum Window Substring?

Because the target length is already known and fixed: a permutation of s1 must be EXACTLY s1.length characters long, no more, no less. There’s nothing to discover about the window’s size — it’s given up front.
That means only one moving boundary is needed conceptually (the right edge), since left is always derived as right - k + 1 — not two independently-moving pointers that each have their own reason to advance.
Contrast with Minimum Window Substring, where the window’s size is exactly what’s being searched for — it has to grow until a condition is satisfied, then shrink to find the minimum, because the target length isn’t known ahead of time.

The optimal solution is described as O(1) amortized per slide, not O(k). Why — what specifically keeps each slide from re-scanning the whole window?

Sliding the window by one position changes the window’s contents by exactly two characters: the one entering on the right, and the one leaving on the left. Every other character already in the window is completely unaffected.
The matches counter is maintained incrementally — each bump() call only re-checks the ONE character it just changed against need, an O(1) comparison, not a full re-derivation of the whole map’s match status.
The trap this avoids: if you instead rebuilt a fresh frequency map from scratch and compared it entirely against need on every slide, that’s O(k) work per slide — O(n·k) overall, not O(n). The incremental matches counter is the entire reason this solution is linear.

What does matches === need.size actually mean, and why compare against need.size instead of s1.length?

need.size is the number of DISTINCT characters in s1 (a Map’s key count) — not the total character count. matches only increments when one specific character’s window count becomes EXACTLY equal to its required count in need.
Comparing against s1.length would be wrong whenever s1 has repeated characters. For s1="aab", need = {a: 2, b: 1}, so need.size is 2 — the window is a full match once BOTH distinct characters hit their required count, regardless of the fact that s1.length is 3.
A window can have the right TOTAL character count (s1.length) while still being the wrong multiset — e.g. window "aaa" against need={a:2,b:1} has 3 characters total but zero bs, so it’s not a match. need.size plus per-character exact-count matching is what actually captures “same multiset,” not a raw length check.

Trick question — this page’s frequency counters (need and window) are deliberately built as Maps, not plain objects ({}). Beyond .has()/.size being nicer to use, is there a real correctness reason to prefer Map for arbitrary string keys?

const obj = {};
['2', '1', 'a', '0'].forEach(k => obj[k] = true);
console.log(Object.keys(obj)); // ?

const m = new Map();
['2', '1', 'a', '0'].forEach(k => m.set(k, true));
console.log(Array.from(m.keys())); // ?

Answer: Object.keys(obj) logs ['0', '1', '2', 'a'] — NOT insertion order. Array.from(m.keys()) logs ['2', '1', 'a', '0'] — exactly insertion order, every time.
Plain JS objects silently reorder their own keys: any key that looks like a valid array index (an integer-like string, e.g. '0', '1', '2') gets sorted numerically and enumerated FIRST, ahead of every other string key, which keeps strict insertion order. Map makes no such distinction — every key, of any type, always stays in insertion order.
This specific problem’s need/window keys are always lowercase letters, so the reordering never actually fires here — but the algorithm’s correctness never depended on iteration order in the first place (only .get/.set/.size are used). The real risk is reusing this exact frequency-map pattern on a problem whose “characters” are digit strings (e.g. counting digits in a numeral string) — a plain object would silently reorder those keys, and code that assumed insertion order (a debug log, a UI rendering the map’s entries in the order counted) would quietly show the wrong order, with no error or exception anywhere.

Quiz

1. For a window of s2 to count as “a permutation of s1,” what actually has to be true about it?

It must contain the exact same characters as s1, with the same counts, in any order
It must be sorted in the same order as a sorted version of s1
It must start with the same character as s1

2. Why is generating every permutation of s1 (even after de-duplicating repeated characters) still described as factorial-time in the worst case?

Because when all of s1’s characters are distinct, there are exactly k! orderings to generate
Because de-duplication always collapses the count down to O(k)
Because sorting the permutations afterward dominates the cost

3. What does the running matches counter in the optimal solution actually track?

The number of distinct characters whose window count exactly equals their required count in need
The total number of characters currently inside the window
How many times the window has slid so far

4. Why is each window slide O(1) amortized instead of O(k) (the window’s width)?

Only two characters’ counts ever change per slide — the one entering and the one leaving — so nothing else needs to be re-checked
Because JavaScript caches the result of the previous slide automatically
Because the window skips ahead by k positions instead of sliding by 1

5. What is the time and space complexity of the optimal fixed-size sliding window solution?

O(n) time, O(1) space — one pass over s2, with frequency maps bounded by the alphabet
O(n·k) time, O(k) space — each slide rescans the whole window
O(k!) time, same as the brute force, just with less memory