# Leetcode 567 - Permutation in String

### Understanding the problem

Given two strings s1 and s2, write a function to check if s2 is a permutation of s1.

Example:

Input: s1 = “ab” s2 = “eidbaooo”

Output: True

Explanation: s2 contains one permutation of s1 (“ba”).

Input: s1 = “ab” s2 = “eidboaoo”

Output: False

Note:

• The input strings only contain lower case letters.
• The length of s1 and s2 must not exceed 10^4.

One approach to solve this problem is to use sliding window technique. We can slide a window of length len(s1) over the string s2 and check if the characters in the window are a permutation of s1. If it is, we return True. Otherwise, we slide the window by one character to the right and repeat the process until we reach the end of s2. If we have checked all the windows and none of them is a permutation of s1, we return False.

Now let’s implement the solution in Python.

First, we need to define the function `check_permutation(s1: str, s2: str) -> bool` that takes in two strings s1 and s2 and returns a boolean indicating if s2 is a permutation of s1.

We can start by initializing a variable `window` to an empty list. This list will store the characters in the current window that we are checking.

Then, we can use a for loop to iterate over the characters in s2. In each iteration, we append the current character to the `window` list. If the length of the `window` list is greater than the length of s1, we remove the first character from the list. This way, the `window` list always stores the characters in the current window that we are checking.

Next, we can use a set and a counter to check if the characters in the `window` list are a permutation of s1. We can create a set `s1_set` from the characters in s1 and a counter `counter` initialized to the length of s1. Then, we can iterate over the characters in the `window` list and check if each character is in the `s1_set`. If it is, we decrement the `counter` by 1. Otherwise, we break the loop and continue with the next iteration.

If the `counter` becomes 0 at the end of the loop, it means that the `window` list contains a permutation of s1, so we return True.

Finally, we return False if we have checked all the windows and none of them is a permutation of s1.

Here is the implementation:

``````from collections import Counter

def checkInclusion(s1: str, s2: str) -> bool:
window = []
for c in s2:
window.append(c)
if len(window) > len(s1):
window.pop(0)
if len(window) == len(s1):
s1_set = set(s1)
counter = len(s1)
for c in window:
if c in s1_set:
counter -= 1
else:
break
if counter == 0:
return True
return False
``````

Now we can test our solution with some test cases.

``````s1 = "ab"
s2 = "eidbaooo"
assert checkInclusion(s1, s2) == True

s1 = "ab"
s2 = "eidboaoo"
assert checkInclusion(s1, s2) == False

s1 = "abc"
s2 = "bac"
assert checkInclusion(s1, s2) == True

s1 = "abc"
s2 = "bcaa"
assert checkInclusion(s1, s2) == True

s1 = "abc"
s2 = "abcd"
assert checkInclusion(s1, s2) == False
``````

All the test cases pass, which means our solution is correct.

That’s it! We have successfully implemented a solution to check if s2 is a permutation of s1 using the sliding window technique.

I hope this helps! Let me know if you have any questions.