The problem statement suggests permutation generation: produce every permutation of s1, then check whether any of them appears as a substring in s2. That works, but the number of permutations of a string of length n is n!, so it is far too slow for the given constraints.

The deciding fact is that two strings are permutations of each other if and only if they have the exact same character frequencies. "ab" and "ba" are permutations because both contain one 'a' and one 'b'. So instead of generating permutations, we need to find a contiguous substring of s2 with length equal to s1 that has the same character frequency distribution as s1.

That turns this into a sliding window problem. We slide a window of size len(s1) across s2, and at each position check whether the window's character frequencies match s1's frequencies.

Key Constraints:

Intuition

The brute force approach follows the problem statement directly: generate every permutation of s1, then check whether any of them appears in s2 as a substring.

It is simple but slow. The number of permutations of a string of length n is n!, which is 3,628,800 for n = 10 and grows quickly after that. For n up to 10^4 this is impractical. It is still useful as a baseline, because the reason it is wasteful points straight at the better approach: every permutation of s1 has identical character frequencies, so generating all of them computes the same frequency profile millions of times.

Algorithm

Example Walkthrough

Take s1 = "ab", s2 = "eidbaooo".

The permutations of "ab" are "ab" and "ba".

A permutation was found, so the function returns true.

For a failing case, take s1 = "ab", s2 = "eidboaoo". Neither "ab" nor "ba" appears among the length-2 substrings "ei", "id", "db", "bo", "oa", "ao", "oo", so both searches fail and the function returns false.

Code

The brute force generates n! permutations, which is too many for even modest string lengths, and every one of them has identical character frequencies. The next approach skips permutation generation and compares character frequencies directly.

Intuition

A permutation is a rearrangement, so two strings are permutations of each other exactly when they contain the same characters with the same counts. Instead of checking every permutation, we look for a window of length len(s1) in s2 whose character frequencies match s1's frequencies.

The window is a fixed size (always len(s1) characters), so we can slide it across s2 one character at a time. When the window moves right, we add the new character entering on the right and remove the character leaving on the left, then compare the two frequency arrays. Rebuilding the window frequency from scratch at each position would cost O(n) per step; the incremental update costs O(1) per step.

With only 26 lowercase letters, comparing two frequency arrays takes constant time. The whole scan runs in O(26 * m) time, which simplifies to O(m).

Algorithm

Example Walkthrough

Take s1 = "ab", s2 = "eidbaooo", so n = 2.

The target frequency from s1 is a:1, b:1 (all other counts zero).

Build the first window s2[0..1] = "ei": window frequency e:1, i:1. Compare against the target: no match.

Now slide. At each step the new character s2[i] enters and s2[i - n] leaves. Only the affected counts are shown.

At i = 4 the window "ba" has frequency a:1, b:1, which equals s1's frequency, so the function returns true.

If s2 were "eidboaoo" instead, the windows would be "ei", "id", "db", "bo", "oa", "ao", "oo". None has frequency a:1, b:1, so the loop finishes and the function returns false.

Code

This approach compares all 26 entries of the frequency arrays at every window position, even though sliding by one position changes only two characters. The next approach tracks how many characters already have matching frequencies and updates that count incrementally, cutting the per-step work to O(1).

Intuition

When the window slides by one, only two frequency entries change: the character entering and the character leaving. The previous approach still re-scans all 26 entries each time, which is wasted work.

Instead, maintain a matches counter that tracks how many of the 26 characters currently have equal frequencies in s1 and the window. When matches == 26, every character frequency agrees, so the window is a permutation of s1.

When a single character's window count changes by one, only that character's match status can flip, and it can flip in one of two ways. After incrementing a count, it either rose to equal s1's count (a new match, so matches++) or rose one past s1's count (it was equal before and now is not, so matches--). Any other change leaves the equality state untouched. The same reasoning applies symmetrically after a decrement. Checking those two conditions per character keeps the per-step work at O(1).

Algorithm

Example Walkthrough

Take s1 = "ab", s2 = "eidbaooo", so n = 2. s1's frequency is a:1, b:1.

Build the first window "ei" (e:1, i:1) and count matches. The two characters a and b disagree (s1 has 1, the window has 0), and e and i disagree (s1 has 0, the window has 1). The remaining 22 letters agree at 0, so matches starts at 22.

Now slide the window. Each step adds s2[i], removes s2[i - n], and adjusts matches.

After the i = 4 step, matches reaches 26. The check at the top of the i = 5 iteration sees matches == 26 and returns true. The window at that point is "ba", which is a permutation of "ab".

Note the check sits at the start of the loop body, so a window that becomes a full match is reported on the next iteration (or by the final return matches == 26 when the matching window is the last one in s2).

Code