## Table of contents

## Open Table of contents

## Problem

Given two strings `s1`

and `s2`

, return `true`

*if* `s2`

*contains a permutation of* `s1`

*, or* `false`

*otherwise*.

In other words, return `true`

if one of `s1`

’s permutations is the substring of `s2`

.

Example 1:

```
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
```

Example 2:

```
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
```

Constraints:

`1 <= s1.length, s2.length <= 104`

`s1`

and `s2`

consist of lowercase English letters.

## Explanation/Approach

The problem requires checking if there is any permutation of string `s1`

that is a substring of `s2`

. This means you have to check if all characters (and their respective counts) in `s1`

are present consecutively in `s2`

.

One efficient approach to solve this problem involves using a sliding window with a hashmap (or frequency counter). We can iterate over `s2`

with a window of size `s1.length()`

, and check if the frequency of characters within this window matches that of `s1`

.

**Approach Steps:**

- First, count the frequency of each character in
`s1`

and store it in a hashmap. - Create a sliding window over
`s2`

of length`s1.length()`

. - Count the frequency of characters within the sliding window and compare it to the frequency hashmap of
`s1`

. - If both frequency maps are equal, return true.
- Otherwise, continue sliding the window over
`s2`

and update the frequency counts accordingly until you find a match or reach the end of`s2`

.

## Solution (Sliding Window Approach)

Below is the detailed code explanation for the sliding window approach.

```
from collections import Counter
def check_inclusion(s1: str, s2: str) -> bool:
# Step 1: Count frequency of each character in s1
s1_count = Counter(s1)
# Step 2: Initialize a sliding window and count characters
window_count = Counter()
for i, c in enumerate(s2):
window_count[c] += 1
# Step 3: If the window size is greater than s1's length, remove leftmost character from count
if i >= len(s1):
left_char = s2[i - len(s1)]
if window_count[left_char] == 1:
del window_count[left_char]
else:
window_count[left_char] -= 1
# Step 4: Compare window_count and s1_count. If they're equal, return True
if window_count == s1_count:
return True
return False # If loop finishes and no return, then no valid substring found
```

**Explanation:**

- We first count the frequency of each character in
`s1`

using a`Counter`

. - Then, we iterate over
`s2`

, counting the frequency of characters within a window of length`s1.length()`

. - For each character added to the window, if the window size exceeds
`s1.length()`

, we remove the leftmost character from the count. - At each step, we compare the count of characters within the window to the count of characters in
`s1`

. If they match, we immediately return`True`

. - If we reach the end of
`s2`

without finding a match, we return`False`

.

**Time and Memory Complexity:**

**Time Complexity:**O(N) where N is the length of`s2`

. Each character in`s2`

is processed once.**Space Complexity:**O(1). The counter will have at most 26 keys (for each letter in the English alphabet), so it uses constant space.