Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

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



Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

Difficulty: interview

Starter code:

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        

Solutions:
class Solution:
     def checkInclusion(self, s1, s2):
         """
         :type s1: str
         :type s2: str
         :rtype: bool
         """
         if len(s2) < len(s1):
             return False
         c1 = [0] * 128
         n = 0
         for i in s1:
             c = ord(i)
             if c1[c] == 0: n += 1
             c1[c] += 1
         for i in range(len(s1)):
             c = ord(s2[i])
             c1[c] -= 1
             if not c1[c]: n -= 1
         if not n: return True
         for i in range(len(s2) - len(s1)):
             c = ord(s2[i])
             if not c1[c]: n += 1
             c1[c] += 1
             c = ord(s2[i + len(s1)])
             c1[c] -= 1
             if not c1[c]:
                 n -= 1
                 if not n: return True
         return False

class Solution:
     def checkInclusion(self, s1, s2):
         """
         :type s1: str
         :type s2: str
         :rtype: bool
         """
         l1, l2 = len(s1), len(s2)
         c1 = [0] * 128
         n = 0
         for i in s1:
             c = ord(i)
             if c1[c] == 0: n += 1
             c1[c] += 1
         for i in range(l2):
             j = i - l1
             if j >= 0:
                 c = ord(s2[j])
                 if not c1[c]: n += 1
                 c1[c] += 1
             c = ord(s2[i])
             c1[c] -= 1
             if not c1[c]:
                 n -= 1
                 if not n: return True
         return False

class Solution:
     def checkInclusion(self, s1, s2):
         """
         :type s1: str
         :type s2: str
         :rtype: bool
         """
         
         if len(s2) < len(s1): return False
         counter = collections.defaultdict(int)
         for c in s1: counter[c] += 1
         
         seen = collections.defaultdict(int)
         
         for i in range(len(s1)-1):
             seen[s2[i]] += 1
 
         right = len(s1)-1
         while right < len(s2):
             seen[s2[right]] += 1
             if seen == counter: return True
             right += 1
             left = right - len(s1)
             seen[s2[left]] -= 1
             if seen[s2[left]] == 0: del seen[s2[left]]
                 
         return False
             


class Solution:
     def checkInclusion(self, s1, s2):
         """
         :type s1: str
         :type s2: str
         :rtype: bool
         """
         length_1 = len(s1)
         length_2 = len(s2)
         if length_1 > length_2:
             return False
         S1_MAP = [0] * 128  # size of ASCII table
         S2_MAP = [0] * 128
         
         # Initialise MAP S1
         
         for char in s1:
             S1_MAP[ord(char)] += 1
         index = 0
         while index < length_1 -1:
             S2_MAP[ord(s2[index])] += 1
             index += 1
         while index < length_2:
             S2_MAP[ord(s2[index])] += 1
             if index >= length_1:
                 S2_MAP[ord(s2[index-length_1])] -= 1
             if S1_MAP == S2_MAP:
                 return True
             index += 1
         return False