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].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Amortized analysis

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

Solutions:
class Solution:

	def checkInclusion(self, s1, s2):
		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):
		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):
		length_1 = len(s1)
		length_2 = len(s2)
		if length_1 > length_2:
			return False
		S1_MAP = [0] * 128
		S2_MAP = [0] * 128
		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