## 1. Description

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.

Constraints:

1. $$1 \leq s1.length, s2.length \leq 10^{4}$$
2. s1 and s2 consist of lowercase English letters

### 1.1. Examples:

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

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


## 2. Solution

### 2.1. Understanding the problem

Well a trivial case is if len(s1) > len(s2), then we return false.

I think we can just use brute force and scan s2 with a sliding window s2[slow:fast], where fast-slow == len(s1), and check if s1 is a permutation of the window.

How to check for permutation? I think we should first check if set(s1) == set(s2[slow:fast]), then check sum([ord(c) for c in s1]) == sum([ord(c) for c in window]).

### 2.3. Code

def checkInclusion(s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""

if len(s1) > len(s2):
return False

fast = 0
slow = 0

while fast - slow < len(s1):
fast += 1

while fast <= len(s2):
window = s2[slow:fast]
if (set(s1) == set(window)) and (
sum([ord(c) for c in s1]) == sum([ord(c) for c in window])
):
return True
fast += 1
slow += 1

return False

# tests
s1 = "abc"
s2 = "a"
print(checkInclusion(s1, s2) == False)

s1 = "abc"
s2 = "abc"
print(checkInclusion(s1, s2) == True)

s1 = "abc"
s2 = "bca"
print(checkInclusion(s1, s2) == True)

s1 = "abc"
s2 = "bcae"
print(checkInclusion(s1, s2) == True)

s1 = "abc"
s2 = "bbcda"
print(checkInclusion(s1, s2) == True)

True
True
True
True
False


#### 2.3.1. Complexity

##### 2.3.1.1. Time complexity:

I'm not too sure about this but I think this is $$O(N^{2})$$ as worst case we need to do $$N \over 2$$ sum during a full scan.

##### 2.3.1.2. Space complexity:

O(N).

### 2.4. Leetcode solution

nil.

<<imports for typing>>