Faangprep Logo
Log inStart free
Browse curriculum

Permutation in String

Check whether s2 contains a permutation of s1 by sliding a fixed window of len(s1) and comparing letter counts.

MediumSolve on LeetCode

Problem Understanding

Permutation in String: return true if s2 contains some permutation of s1 as a contiguous substring.

Examples: s1 = "ab", s2 = "eidbaooo" returns true because "ba" appears in s2. s1 = "ab", s2 = "eidboaoo" returns false.

The Intuition: Same Length, Same Counts

A permutation of s1 has exactly len(s1) letters and exactly the same letter counts as s1. So the question becomes: does any window of s2 with length len(s1) have the same counts as s1?

That is a fixed-size sliding window:

  1. Count s1 into need[26].
  2. Walk s2: add the letter entering on the right; once the window is longer than len(s1), remove the letter leaving on the left.
  3. If the window's counts equal need, return true.

Sorting each window would work too, but costs O(k log k) per step; updating two counts is O(1). The same counting idea solves Valid Anagram for whole strings.

Interactive Walkthrough

The window over s2 is shaded, and the letter just added or dropped is filled. The table below counts each letter in s1 and in the window; columns that already agree are dimmed, so you can see exactly which letters are still off.

Dry Run Table

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

i Window Counts equal?
1 ei no
2 id no
3 db no
4 ba yes

The window "ba" matches, so the answer is true.

The Solution Template

Two count arrays and a fixed window of len(s1).

Permutation in String Code
1var checkInclusion = function(s1, s2) {
2    if (s1.length > s2.length) return false;
3    const need = new Array(26).fill(0), window = new Array(26).fill(0);
4    for (const c of s1) need[c.charCodeAt(0) - 97]++;
5    for (let i = 0; i < s2.length; i++) {
6        window[s2.charCodeAt(i) - 97]++;
7        if (i >= s1.length) window[s2.charCodeAt(i - s1.length) - 97]--;
8        if (window.every((v, k) => v === need[k])) return true;
9    }
10    return false;
11};

Edge Cases & Common Mistakes

  • s1 longer than s2: no window fits; return false first.
  • Repeated letters: counts, not sets, are compared; "aab" needs two a's in the window.
  • Removing the wrong letter: the letter leaving is s2[i − len(s1)], once i ≥ len(s1).
  • Comparing only after the window is full: comparing earlier is harmless, because a partial window can never equal need.

Summary

A permutation of s1 is a window of s2 with length len(s1) and the same letter counts. Slide that window across s2, adding the letter on the right and removing the one on the left, and compare the two 26-letter count arrays after each step. O(n) time, O(1) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Maximum Sum of Distinct Subarrays With Length K

Next

Find All Anagrams in a String

The approach, step by step

  1. Count s1

    If s1 is longer than s2, return false. Otherwise count s1's letters into need[26].

  2. Slide a window over s2

    Add s2[i] to window; once i ≥ len(s1), remove s2[i − len(s1)].

  3. Compare

    After each step, return true if window equals need. Return false at the end.

Frequently asked questions

Why does comparing letter counts find a permutation?

Two strings are permutations of each other exactly when they contain the same letters the same number of times. So a window of s2 with length len(s1) is a permutation of s1 when its 26 counts equal s1's counts.

Why is the window a fixed size?

A permutation of s1 has exactly len(s1) letters, so only windows of that length can match. Each step adds the letter entering on the right and removes the one leaving on the left.

Can the comparison be O(1) per step?

Yes. Keep a count of how many of the 26 letters currently match, and update it only for the two letters that change each step. The answer is true when all 26 match. Comparing the arrays directly is O(26) per step, which is still linear overall.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description