Permutation in String

1. Define the problem

Given strings s1 and s2, return true if s2 contains a permutation of s1 as a contiguous substring . Slide a fixed-size window of length s1 across s2 and compare letter frequency counts as one character leaves and another enters.

Constraints

1 ≤ s1.length, s2.length ≤ 10⁴
s1 and s2 consist of lowercase English letters

Example

Inputs1 = "ab", s2 = "eidbaooo"

Outputtrue

Explanation "ba" is a permutation of "ab" and appears in s2.

2. Know the words first

In plain terms

Permutation: A rearrangement of all the letters in a word or phrase, using each one exactly once — 'ab' and 'ba' are permutations of each other.

3. Visualize the solution

Fixed window matching s1 letter counts

Statusmiss

Window "ei" — counts do not match need {a:1,b:1}.

What happens in this step

window = [0, 1]  ("ei")   need = {a:1, b:1}

built from s2[0..1]:
  window = {e:1, i:1}

window counts {e:1, i:1} don't match need {a:1, b:1} — no permutation here yet.

Step 1 of 4

Steps to visualize

Build need counts from s1 and a same-size window over the start of s2.
If the window letter counts match need, return true.
Slide one step: increment the entering char, decrement the leaving char.
Compare counts after each slide.
Return false if no window ever matches.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fixed window matching s1 letter counts

Statusmiss

Window "ei" — counts do not match need {a:1,b:1}.

What happens in this step

window = [0, 1]  ("ei")   need = {a:1, b:1}

built from s2[0..1]:
  window = {e:1, i:1}

window counts {e:1, i:1} don't match need {a:1, b:1} — no permutation here yet.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function checkInclusion(s1, s2) {
  const n = s1.length;
  const m = s2.length;
  if (n > m) return false;

  const need = new Array(26).fill(0);
  const window = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);

  for (let i = 0; i < n; i++) {
    need[s1.charCodeAt(i) - a]++;
    window[s2.charCodeAt(i) - a]++;
  }

  const matches = () => {
    for (let i = 0; i < 26; i++) {
      if (need[i] !== window[i]) return false;
    }
    return true;
  };

  if (matches()) return true;

  for (let right = n; right < m; right++) {
    window[s2.charCodeAt(right) - a]++;
    const left = right - n;
    window[s2.charCodeAt(left) - a]--;
    if (matches()) return true;
  }

  return false;
}

Time: O(n)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`s1 = "ab", s2 = "eidbaooo"`	`true`	Docstring example — "ba" is a permutation
`s1 = "a", s2 = "a"`	`true`	Smallest valid input
`s1 = "abc", s2 = "bca"`	`true`	Entire s2 is a permutation of s1
`s1 = "ab", s2 = "eidboaoo"`	`false`	No valid window exists
`s1 = "aaa", s2 = "aaaaa"`	`true`	All identical characters with exact count match
`s1 = "abcd", s2 = "abc"`	`false`	s1 longer than s2
`s1 = "abc", s2 = "xyzxycab"`	`true`	Permutation "cab" appears later in s2

Permutation in String