At first glance, this looks like a permutation generation problem. You might think: generate all permutations of s1, then check if any of them appears as a substring in s2. That would work, but it's wildly inefficient.

The key observation is this: 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 just 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. 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 most literal reading of the problem says "return true if one of s1's permutations is a substring of s2." So the brute force approach does exactly that: generate every permutation of s1, then check if any of them appears in s2 as a substring.

This is conceptually simple but catastrophically slow. The number of permutations of a string of length n is n!, which is 3,628,800 for n = 10 and grows astronomically from there. For the given constraint of n up to 10^4, this approach is completely impractical. But it's worth understanding as a starting point to see why we need a smarter approach.

Algorithm

Code

The brute force generates n! permutations, which is astronomical for even modest string lengths. But every permutation of a string has the exact same character frequencies, so all that computation is redundant. What if we skipped permutation generation entirely and just compared character frequencies directly?

Intuition

Here's the key insight that changes everything: two strings are permutations of each other if and only if they have identical character frequencies. "abc" and "bca" both have exactly one 'a', one 'b', and one 'c'. So instead of checking every permutation, we just need to find a window of length len(s1) in s2 whose character frequency matches s1's frequency.

Since we're looking at a fixed-size window (always len(s1) characters), we can slide it across s2 one character at a time. When the window moves right, we add the new character entering the window and remove the character leaving the window. Then we compare the two frequency arrays.

With only 26 lowercase letters, comparing two frequency arrays is a constant-time operation. So the whole thing runs in O(26 * m) time, which is effectively O(m).

Algorithm

Code

This approach works well, but at every window position we compare all 26 entries of the two frequency arrays. When the window slides by one position, only two characters change. What if we tracked how many characters already have matching frequencies and updated that count incrementally?

Intuition

The previous approach compares all 26 frequency entries at every window position. But when the window slides by one, only two characters are affected: the one entering and the one leaving. So at most two frequency entries change. Comparing all 26 entries is overkill.

The optimization is to 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, meaning the window is a permutation of s1.

When a character enters or leaves the window, we check whether that specific character's match status changed (from matching to not matching, or vice versa) and update the counter accordingly. This reduces the per-step work from O(26) to O(1).

Algorithm

Code