Given a word pat and a text txt. Return the count of the occurrences of anagrams of the word in the text.
Example 1:
Input:
txt = forxxorfxdofr
pat = for
Output: 3
Explanation: for, orf and ofr appears
in the txt, hence answer is 3.
Example 2:
Input:
txt = aabaabaa
pat = aaba
Output: 4
Explanation: aaba is present 4 times
in txt.
Your Task:
Complete the function search() which takes two strings pat, txt, as input parameters and returns an integer denoting the answer. 
You don't need to print answer or take inputs.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(26) or O(256)
Constraints:
1 <= |pat| <= |txt| <= 10^{5}
Both strings contain lowercase English letters.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3

class Solution:



	

	def search(self,pat, txt):

	    # code here

Solutions:
class Solution:

	def search(self, pat, txt):
		k = 0
		d_pat = {}
		for i in pat:
			if i in d_pat:
				d_pat[i] += 1
			else:
				d_pat[i] = 1
			k += 1
		d_txt = {}
		n = len(txt)
		(i, j) = (0, 0)
		c = 0
		while j < n:
			if txt[j] in d_txt:
				d_txt[txt[j]] += 1
			else:
				d_txt[txt[j]] = 1
			if j - i + 1 == k:
				if d_pat == d_txt:
					c += 1
				d_txt[txt[i]] -= 1
				if d_txt[txt[i]] == 0:
					del d_txt[txt[i]]
				i += 1
			j += 1
		return c


from collections import defaultdict

class Solution:

	def search(self, pat, txt):
		(n, k) = (len(txt), len(pat))
		d = defaultdict(int)
		for i in pat:
			d[i] += 1
		count = len(d)
		i = 0
		j = 0
		anagrams = 0
		while i <= n - 1:
			d[txt[i]] -= 1
			if d[txt[i]] == 0:
				count -= 1
			if i < k - 1:
				i += 1
			else:
				if count == 0:
					anagrams += 1
				if d[txt[j]] == 0:
					count += 1
				d[txt[j]] += 1
				i += 1
				j += 1
		return anagrams


class Solution:

	def search(self, pat, txt):
		d = {}
		for i in pat:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		count = len(d)
		res = 0
		(i, j) = (0, 0)
		k = len(pat)
		n = len(txt)
		while j < n:
			if txt[j] in d:
				d[txt[j]] -= 1
				if d[txt[j]] == 0:
					count -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if count == 0:
					res += 1
				if txt[i] in d:
					d[txt[i]] += 1
					if d[txt[i]] == 1:
						count += 1
				i += 1
				j += 1
		return res


class Solution:

	def search(self, pat, txt):
		alpha = 'qwertyuiopasdfghjklzxcvbnm'
		mp = {}
		nmap = {}
		for i in alpha:
			mp[i] = 0
			nmap[i] = 0
		for i in pat:
			mp[i] += 1
		ans = 0
		j = len(pat)
		for i in range(len(pat)):
			nmap[txt[i]] += 1
		for i in range(len(txt) - len(pat)):
			if nmap == mp:
				ans += 1
			nmap[txt[i]] -= 1
			nmap[txt[j]] += 1
			j += 1
		if nmap == mp:
			ans += 1
		return ans


class Solution:

	def search(self, pat, txt):
		d = {}
		for i in pat:
			if i not in d.keys():
				d[i] = 1
			else:
				d[i] += 1
		i = 0
		j = 0
		count = 0
		while j < len(txt):
			if txt[j] in d.keys():
				d[txt[j]] -= 1
			if j - i + 1 < len(pat):
				j += 1
			elif j - i + 1 == len(pat):
				flag = True
				for k in d.keys():
					if d[k] != 0:
						flag = False
				if flag:
					count += 1
				if txt[i] in pat:
					d[txt[i]] += 1
				i += 1
				j += 1
		return count


class Solution:

	def search(self, pat, txt):
		h = {}
		for i in pat:
			h[i] = 1 + h.get(i, 0)
		(i, j) = (0, 0)
		K = len(pat)
		tmp = {}
		c = 0
		while j < len(txt):
			tmp[txt[j]] = 1 + tmp.get(txt[j], 0)
			if j - i + 1 < K:
				j += 1
			elif j - i + 1 == K:
				if tmp == h:
					c += 1
				firstChar = txt[i]
				tmp[firstChar] -= 1
				if tmp[firstChar] == 0:
					del tmp[firstChar]
				i += 1
				j += 1
		return c


class Solution:

	def search(self, pat, txt):
		K = len(pat)
		letters = dict()
		temp = list()
		occurences = 0
		if K == 1:
			for i in range(0, len(txt)):
				if txt[i] == pat[0]:
					occurences += 1
			return occurences
		for i in range(0, K):
			letters[pat[i]] = letters.get(pat[i], 0) + 1
		i = 0
		j = 0
		count = len(letters)
		while j < len(txt):
			if txt[j] in letters:
				letters[txt[j]] -= 1
				if letters[txt[j]] == 0:
					count -= 1
			if j - i + 1 == K:
				if count == 0:
					occurences += 1
				if txt[i] in letters:
					letters[txt[i]] += 1
					if letters[txt[i]] == 1:
						count += 1
				i += 1
			j += 1
		return occurences


class Solution:

	def search(self, pat, txt):
		k = len(pat)
		d = {}
		r = {}
		ws = 0
		we = 0
		count = 0
		for i in pat:
			d[i] = d.get(i, 0) + 1
		while we < len(txt):
			if txt[we] in r:
				r[txt[we]] += 1
			else:
				r[txt[we]] = 1
			if we - ws + 1 == k:
				if r == d:
					count += 1
				if r[txt[ws]] == 1:
					del r[txt[ws]]
				else:
					r[txt[ws]] -= 1
				ws += 1
			we += 1
		return count


class Solution:

	def search(self, pat, txt):
		freq = {}
		window = len(pat)
		output = 0
		i = 0
		while i < len(pat):
			if pat[i] not in freq:
				freq[pat[i]] = 1
			else:
				freq[pat[i]] += 1
			i += 1
		(i, j) = (0, 0)
		count = len(freq)
		while j < len(txt):
			if txt[j] in freq:
				freq[txt[j]] -= 1
				if freq[txt[j]] == 0:
					count -= 1
			if j - i + 1 < window:
				j += 1
			elif j - i + 1 == window:
				if count == 0:
					output += 1
				if txt[i] in freq:
					freq[txt[i]] += 1
					if freq[txt[i]] == 1:
						count += 1
				j += 1
				i += 1
		return output


from collections import Counter

class Solution:

	def search(self, pat, txt):
		if len(pat) > len(txt):
			return 0
		pat_count = Counter(pat)
		txt_count = Counter(txt[:len(pat)])
		c = 0
		if pat_count == txt_count:
			c += 1
		for i in range(len(pat), len(txt)):
			txt_count[txt[i]] += 1
			txt_count[txt[i - len(pat)]] -= 1
			if txt_count[txt[i - len(pat)]] == 0:
				del txt_count[txt[i - len(pat)]]
			if pat_count == txt_count:
				c += 1
		return c


class Solution:

	def search(self, pat, txt):
		p = [0] * 26
		for i in pat:
			p[ord(i) - 97] += 1
		ans = [0] * 26
		wend = 0
		wstart = 0
		c = 0
		while wend < len(txt):
			ans[ord(txt[wend]) - 97] += 1
			if wend - wstart + 1 == len(pat):
				if ans == p:
					c += 1
				ans[ord(txt[wstart]) - 97] -= 1
				wstart += 1
			wend += 1
		return c


class Solution:

	def search(self, pat, txt):
		k = len(pat)
		main = {}
		temp = {}
		for i in pat:
			if i not in main:
				main[i] = 1
			else:
				main[i] += 1
		s_end = s_srt = count = 0
		while s_end < len(txt):
			if txt[s_end] in main:
				if txt[s_end] in temp:
					temp[txt[s_end]] += 1
				else:
					temp[txt[s_end]] = 1
			if s_end - s_srt + 1 == k:
				if temp == main:
					count += 1
				if txt[s_srt] in temp:
					temp[txt[s_srt]] -= 1
				s_srt += 1
			s_end += 1
		return count


class Solution:

	def search(self, pat, txt):
		c = 0
		d = dict()
		alpha = 'abcdefghijklmnopqrstuvwxyz'
		for ele in alpha:
			d[ele] = 0
		for ele in pat:
			d[ele] = d[ele] + 1
		d2 = dict()
		for ele in alpha:
			d2[ele] = 0
		for i in range(len(pat)):
			d2[txt[i]] = d2[txt[i]] + 1
		j = len(pat) - 1
		i = 0
		while j < len(txt):
			if d2 == d:
				c = c + 1
			d2[txt[i]] = d2[txt[i]] - 1
			i = i + 1
			j = j + 1
			if j < len(txt):
				d2[txt[j]] = d2[txt[j]] + 1
		return c


class Solution:

	def search(self, pat, txt):
		(a, j, count) = (0, 0, 0)
		d = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
		k = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
		size = len(pat)
		for i in pat:
			if i not in d:
				d[i] = 1
			else:
				d[i] = d[i] + 1
		while j < len(txt):
			if txt[j] not in k:
				k[txt[j]] = 1
			else:
				k[txt[j]] = k[txt[j]] + 1
			if j - a + 1 < size:
				j = j + 1
			else:
				if d == k:
					count = count + 1
				k[txt[a]] = k[txt[a]] - 1
				a = a + 1
				j = j + 1
		return count


class Solution:

	def search(self, pat, txt):
		count = 0
		map_pattern = {}
		for ch in pat:
			if ch in map_pattern:
				map_pattern[ch] += 1
			else:
				map_pattern[ch] = 1
		map_text = {}
		i = 0
		j = 0
		for x in range(len(pat)):
			if txt[j] in map_text:
				map_text[txt[j]] += 1
			else:
				map_text[txt[j]] = 1
			j += 1
		if map_text == map_pattern:
			count += 1
		j -= 1
		for x in range(len(txt) - len(pat)):
			if txt[j + 1] in map_text:
				map_text[txt[j + 1]] += 1
			else:
				map_text[txt[j + 1]] = 1
			map_text[txt[i]] -= 1
			if map_text[txt[i]] == 0:
				map_text.pop(txt[i])
			if map_text == map_pattern:
				count += 1
			i += 1
			j += 1
		return count


class Solution:

	def search(self, pat, txt):
		K = len(pat)
		N = len(txt)
		counts = {}
		for c in pat:
			counts[c] = counts.get(c, 0) + 1
		i = 0
		j = 0
		count = len(counts)
		anagramCount = 0
		while j < N:
			if txt[j] in counts:
				counts[txt[j]] = counts.get(txt[j]) - 1
				if counts[txt[j]] == 0:
					count -= 1
			if j - i + 1 < K:
				j += 1
			elif j - i + 1 == K:
				if count == 0:
					anagramCount += 1
				if txt[i] in counts:
					counts[txt[i]] = counts.get(txt[i]) + 1
					if counts[txt[i]] == 1:
						count += 1
				i += 1
				j += 1
		return anagramCount


class Solution:

	def search(self, pat, txt):
		K = len(pat)
		N = len(txt)
		counts1 = {}
		counts2 = {}
		for c in pat:
			counts1[c] = counts1.get(c, 0) + 1
		i = 0
		j = 0
		anagramCount = 0
		while j < N:
			counts2[txt[j]] = counts2.get(txt[j], 0) + 1
			if j - i + 1 < K:
				j += 1
			elif j - i + 1 == K:
				if counts1 == counts2:
					anagramCount += 1
				counts2[txt[i]] = counts2.get(txt[i]) - 1
				if counts2[txt[i]] == 0:
					del counts2[txt[i]]
				i += 1
				j += 1
		return anagramCount


class Solution:

	def search(self, pat, txt):
		arr = []
		pet = []
		c = 0
		for i in range(26):
			pet.append(0)
			arr.append(0)
		for i in range(len(pat)):
			pet[ord(pat[i]) - 97] += 1
		for i in range(len(pat)):
			arr[ord(txt[i]) - 97] += 1
		for i in range(len(pat), len(txt)):
			if pet == arr:
				c += 1
			arr[ord(txt[i - len(pat)]) - 97] -= 1
			arr[ord(txt[i]) - 97] += 1
		if arr == pet:
			c += 1
		return c


class Solution:

	def cmp(self, h1, h2):
		for (i, j) in h1.items():
			if i not in h2 or h1[i] != h2[i]:
				return False
		return True

	def search(self, pat, txt):
		hmp = {}
		lg = 0
		for i in pat:
			lg += 1
			if i in hmp:
				hmp[i] += 1
			else:
				hmp[i] = 1
		c = i = j = 0
		hmp1 = {}
		while j < len(txt):
			if txt[j] in hmp1:
				hmp1[txt[j]] += 1
			else:
				hmp1[txt[j]] = 1
			if j - i == lg - 1:
				if self.cmp(hmp, hmp1):
					c += 1
				if txt[i] in hmp1:
					if hmp1[txt[i]] == 1:
						del hmp1[txt[i]]
					else:
						hmp1[txt[i]] -= 1
				i += 1
			j += 1
		return c


from collections import *

class Solution:

	def search(self, pat, txt):
		i = 0
		j = 0
		d = dict(Counter(pat))
		k = len(pat)
		ans = 0
		temp = {}
		while i < len(txt) - k + 1 and j < len(txt):
			if txt[j] not in temp:
				temp[txt[j]] = 1
			else:
				temp[txt[j]] += 1
			if j - i + 1 == k:
				if temp == d:
					ans += 1
				temp[txt[j - k + 1]] -= 1
				if temp[txt[j - k + 1]] == 0:
					temp.pop(txt[j - k + 1])
				i += 1
			j += 1
		return ans


class Solution:

	def search(self, pat, txt):
		freq = [0] * 26
		freqOfPat = [0] * 26
		for i in range(len(pat)):
			freqOfPat[ord(pat[i]) - 97] += 1
		(start, end, occurrence) = (0, 0, 0)
		temp = []
		while end < len(txt):
			temp.append(txt[end])
			freq[ord(txt[end]) - 97] += 1
			if end - start + 1 == len(pat):
				if freq == freqOfPat:
					occurrence += 1
				freq[ord(temp[0]) - 97] -= 1
				temp.pop(0)
				start += 1
			end += 1
		return occurrence


from collections import deque

class Solution:

	def search(self, pat, txt):
		win = len(pat)
		dic = dict()
		for i in pat:
			dic[i] = dic.get(i, 0) + 1
		temp_dic = dict()
		count = 0
		q = list()
		i = 0
		while i < len(txt):
			if q and i - q[0] == win:
				if temp_dic[txt[q[0]]] == 1:
					temp_dic.pop(txt[q[0]])
				else:
					temp_dic[txt[q[0]]] -= 1
				q.pop(0)
			temp_dic[txt[i]] = temp_dic.get(txt[i], 0) + 1
			q.append(i)
			if i >= win - 1:
				if dic == temp_dic:
					count += 1
			i += 1
		return count


class Solution:

	def search(self, pat, txt):
		alpha = 'abcdefghijklmnopqrstuvwxyz'
		m1 = {}
		m2 = {}
		for i in alpha:
			m1[i] = 0
			m2[i] = 0
		for i in pat:
			m1[i] += 1
		ans = 0
		j = len(pat)
		for i in range(len(pat)):
			m2[txt[i]] += 1
		for i in range(len(txt) - len(pat)):
			if m2 == m1:
				ans += 1
			m2[txt[i]] -= 1
			m2[txt[j]] += 1
			j += 1
		if m2 == m1:
			ans += 1
		return ans


class Solution:

	def search(self, pat, txt):
		k = len(pat)
		n = len(txt)
		dic = {}
		for i in range(k):
			if pat[i] in dic:
				dic[pat[i]] += 1
			else:
				dic[pat[i]] = 1
		i = 0
		j = 0
		count = 0
		isZero = len(dic)
		while j < n:
			if txt[j] in dic:
				dic[txt[j]] -= 1
				if dic[txt[j]] == 0:
					isZero -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if isZero == 0:
					count += 1
				if txt[i] in dic:
					if dic[txt[i]] == 0:
						isZero += 1
					dic[txt[i]] += 1
				i += 1
				j += 1
		return count


class Solution:

	def search(self, p, s):
		(n, m) = (len(s), len(p))
		p_freq = {}
		for c in p:
			p_freq[c] = p_freq.get(c, 0) + 1
		s_freq = {}
		count = 0
		for i in range(n):
			s_freq[s[i]] = s_freq.get(s[i], 0) + 1
			if i >= m:
				if s_freq[s[i - m]] == 1:
					del s_freq[s[i - m]]
				else:
					s_freq[s[i - m]] -= 1
			if i >= m - 1 and s_freq == p_freq:
				count += 1
		return count


class Solution:

	def search(self, pat, txt):
		(wstart, wend) = (0, 0)
		r = [0] * 26
		ans = 0
		l = [0] * 26
		for each in pat:
			r[ord(each) - ord('a')] += 1
		while wend < len(txt):
			l[ord(txt[wend]) - ord('a')] += 1
			if wend - wstart + 1 == len(pat):
				flag = True
				for i in range(26):
					if l[i] != r[i]:
						flag = False
						break
				if flag:
					ans += 1
				l[ord(txt[wstart]) - ord('a')] -= 1
				wstart += 1
			wend += 1
		return ans


from collections import Counter

class Solution:

	def search(self, pat, arr):
		ans = 0
		i = 0
		j = 0
		k = len(pat)
		dic = Counter(pat)
		ct = len(dic)
		while j < len(arr):
			if arr[j] in dic:
				dic[arr[j]] -= 1
				if dic[arr[j]] == 0:
					ct -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if ct == 0:
					ans += 1
				if arr[i] in dic:
					dic[arr[i]] += 1
					if dic[arr[i]] == 1:
						ct += 1
				i += 1
				j += 1
		return ans


class Solution:

	def search(self, pat, txt):
		l = ''
		k = len(pat)
		c = 0
		dic = {}
		for i in pat:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		c = len(dic)
		ans = 0
		i = 0
		j = 0
		while j < len(txt):
			l += txt[j]
			if txt[j] in dic:
				dic[txt[j]] -= 1
				if dic[txt[j]] == 0:
					c -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if c == 0:
					ans += 1
				if l[0] in dic:
					dic[l[0]] += 1
					if dic[l[0]] == 1:
						c += 1
				l = l[1:]
				i += 1
				j += 1
		return ans


from collections import Counter, defaultdict

class Solution:

	def search(self, pat, txt):
		k = len(pat)
		n = len(txt)
		occurance = Counter(pat)
		c = 0
		i = j = 0
		check = defaultdict(lambda : 0)
		res = 0
		while j < n:
			c += 1
			check[txt[j]] += 1
			if c == k:
				flag = 0
				for item in occurance:
					if occurance[item] != check[item]:
						flag = 1
						break
				if flag == 0:
					res += 1
				check[txt[i]] -= 1
				i += 1
				c -= 1
			j += 1
		return res


class Solution:

	def search(self, pat, txt):
		n = len(txt)
		i = 0
		j = 0
		d = dict()
		ans = 0
		k = len(pat)
		for l in pat:
			if l in d:
				d[l] += 1
			else:
				d[l] = 1
		count = len(d)
		while j < n:
			if txt[j] in pat:
				d[txt[j]] -= 1
				if d[txt[j]] == 0:
					count -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if count == 0:
					ans += 1
				if txt[i] in d:
					d[txt[i]] += 1
					if d[txt[i]] == 1:
						count += 1
				i += 1
				j += 1
		return ans


class Solution:

	def search(self, pat, txt):
		hsh = [0] * 26
		win_size = len(pat)
		for i in pat:
			hsh[ord(i) - 97] += 1
		p = len(pat)
		n = len(txt)
		tmp = [0] * 26
		for i in range(p):
			tmp[ord(txt[i]) - 97] += 1
		cnt = 0
		if tmp == hsh:
			cnt += 1
		i = win_size
		while i < n:
			tmp[ord(txt[i - p]) - 97] -= 1
			tmp[ord(txt[i]) - 97] += 1
			if tmp == hsh:
				cnt += 1
			i += 1
		return cnt


from collections import Counter

class Solution:

	def search(self, p, s):
		res = 0
		c = Counter(p)
		cur = Counter(s[:len(p)])
		for i in range(len(s) - len(p) + 1):
			if cur == c:
				res += 1
			if i == len(s) - len(p):
				break
			cur[s[i]] -= 1
			if cur[s[i]] == 0:
				del cur[s[i]]
			cur[s[i + len(p)]] += 1
		return res


from collections import defaultdict

class Solution:

	def search(self, pat, txt):
		(m, n) = (len(pat), len(txt))
		pat_freq = defaultdict(int)
		window_freq = defaultdict(int)
		count = 0
		for c in pat:
			pat_freq[c] += 1
		for i in range(m):
			window_freq[txt[i]] += 1
		for i in range(m, n):
			if window_freq == pat_freq:
				count += 1
			window_freq[txt[i]] += 1
			window_freq[txt[i - m]] -= 1
			if window_freq[txt[i - m]] == 0:
				del window_freq[txt[i - m]]
		if window_freq == pat_freq:
			count += 1
		return count


class Solution:

	def search(self, pat, txt):
		k = len(pat)
		n1 = len(txt)
		count = 0
		dicti = {}
		for i in pat:
			if i not in dicti:
				dicti[i] = 1
			else:
				dicti[i] += 1
		count1 = len(dicti)
		(i, j) = (0, 0)
		while j < n1:
			if txt[j] in dicti:
				dicti[txt[j]] -= 1
				if dicti[txt[j]] == 0:
					count1 -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if count1 == 0:
					count += 1
				if txt[i] in dicti:
					dicti[txt[i]] += 1
					if dicti[txt[i]] == 1:
						count1 += 1
				i += 1
				j += 1
		return count


class Solution:

	def search(self, b, a):
		k = len(b)
		d = dict()
		i = 0
		j = 0
		count = 0
		ans = 0
		for p in b:
			if p not in d:
				d[p] = 1
			else:
				d[p] += 1
		count = len(d)
		while j < len(a):
			if a[j] in b:
				d[a[j]] -= 1
				if d[a[j]] == 0:
					count -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if count == 0:
					ans += 1
				if a[i] in d:
					d[a[i]] += 1
					if d[a[i]] == 1:
						count += 1
				i += 1
				j += 1
		return ans


from collections import Counter

class Solution:

	def search(self, pat, txt):
		i = 0
		j = 0
		pat_freq = {}
		for c in pat:
			pat_freq[c] = pat_freq.get(c, 0) + 1
		distinct_chars = len(pat_freq)
		occurrence_count = 0
		while j < len(txt):
			if txt[j] in pat_freq:
				pat_freq[txt[j]] -= 1
				if pat_freq[txt[j]] == 0:
					distinct_chars -= 1
			if j - i + 1 < len(pat):
				j += 1
			elif j - i + 1 == len(pat):
				if distinct_chars == 0:
					occurrence_count += 1
				if txt[i] in pat_freq:
					pat_freq[txt[i]] += 1
					if pat_freq[txt[i]] == 1:
						distinct_chars += 1
				i += 1
				j += 1
		return occurrence_count


class Solution:

	def search(self, pat, txt):
		i = 0
		j = 0
		ans = 0
		n = len(txt)
		k = len(pat)
		sub = ''
		dic = {}
		dic1 = {}
		for let in pat:
			if let in dic1:
				dic1[let] += 1
			else:
				dic1[let] = 1
		while j < n:
			if txt[j] in dic:
				dic[txt[j]] += 1
			else:
				dic[txt[j]] = 1
			if j - i + 1 < k:
				j += 1
			else:
				flag = 1
				for let in dic1:
					if let not in dic or dic1[let] != dic[let]:
						flag = 0
				if flag == 1:
					ans += 1
				dic[txt[i]] -= 1
				i += 1
				j += 1
		return ans


class Solution:

	def isCheck(self, a, b):
		for i in range(len(a)):
			if a[i] != b[i]:
				return False
		return True

	def search(self, pat, txt):
		patArr = [0 for i in range(256)]
		txtArr = [0 for i in range(256)]
		left = 0
		right = 0
		count = 0
		n = len(txt)
		k = len(pat)
		for i in pat:
			patArr[ord(i) - ord('a')] += 1
		while right < n:
			txtArr[ord(txt[right]) - ord('a')] += 1
			if right - left + 1 == k:
				if self.isCheck(patArr, txtArr):
					count += 1
				txtArr[ord(txt[left]) - ord('a')] -= 1
				left += 1
			right += 1
		return count


class Solution:

	def search(self, pat, txt):
		(n, m) = (len(txt), len(pat))
		count = 0
		p = [0] * 26
		t = [0] * 26
		for i in pat:
			p[ord(i) - 97] += 1
		for i in range(m):
			t[ord(txt[i]) - 97] += 1
		for i in range(n - m):
			if p == t:
				count += 1
			t[ord(txt[i]) - 97] -= 1
			t[ord(txt[i + m]) - 97] += 1
		if p == t:
			count += 1
		return count


class Solution:

	def search(self, pat, arr):
		import numpy as np
		i = 0
		j = 0
		k = len(pat)
		d = {}
		c = 0
		for z in pat:
			d[z] = 1 + d.get(z, 0)
		while j < len(arr):
			if arr[j] in d:
				d[arr[j]] = d[arr[j]] - 1
			if j - i + 1 < k:
				j = j + 1
			elif j - i + 1 == k:
				if not np.any(list(d.values())):
					c = c + 1
				if arr[i] in d:
					d[arr[i]] = d[arr[i]] + 1
				i = i + 1
				j = j + 1
		return c


class Solution:

	def search(self, pattern, string):
		start = 0
		end = 0
		n = len(string)
		count = 0
		pat = {}
		curr_pat = {}
		for i in pattern:
			if i in pat:
				pat[i] += 1
			else:
				pat[i] = 1
		while end < n:
			if string[end] in curr_pat:
				curr_pat[string[end]] += 1
			else:
				curr_pat[string[end]] = 1
			if end - start + 1 < len(pattern):
				end += 1
			elif end - start + 1 == len(pattern):
				if curr_pat == pat:
					count += 1
				if string[start] in curr_pat:
					if curr_pat[string[start]] > 1:
						curr_pat[string[start]] -= 1
					else:
						curr_pat.pop(string[start])
				start += 1
				end += 1
		return count


class Solution:

	def search(self, pat, txt):
		i = j = 0
		ans = 0
		k = len(pat)
		d = {}
		for x in range(k):
			if pat[x] not in d:
				d[pat[x]] = 1
			else:
				d[pat[x]] += 1
		count = len(d)
		while j < len(txt):
			if txt[j] in d:
				d[txt[j]] -= 1
				if d[txt[j]] == 0:
					count -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if count == 0:
					ans += 1
				if txt[i] in d:
					d[txt[i]] += 1
					if d[txt[i]] == 1:
						count += 1
				j += 1
				i += 1
		return ans


from collections import deque, Counter

class Solution:

	def search(self, pat, txt):
		if len(pat) > len(txt):
			return 0
		txt = list(txt.strip())
		pat = list(pat.strip())
		count = 0
		k = len(pat)
		curr = deque(txt[:k])
		curr_counts = Counter(curr)
		pat_counts = Counter(pat)
		if curr_counts == pat_counts:
			count += 1
		for i in range(len(txt) - k):
			left_char = curr.popleft()
			curr_counts[left_char] -= 1
			if curr_counts[left_char] == 0:
				del curr_counts[left_char]
			right_char = txt[i + k]
			curr.append(right_char)
			curr_counts[right_char] += 1
			if curr_counts == pat_counts:
				count += 1
		return count


class Solution:

	def search(self, pat, txt):
		i = 0
		d = {}
		t = 0
		for k in pat:
			d[k] = d.get(k, 0) + 1
		c = len(d)
		for j in range(len(txt)):
			if txt[j] in d:
				d[txt[j]] -= 1
				if d[txt[j]] == 0:
					c -= 1
			if j - i + 1 == len(pat):
				if c == 0:
					t += 1
				if txt[i] in d:
					if d[txt[i]] == 0:
						c += 1
					d[txt[i]] += 1
				i += 1
		return t


class Solution:

	def search(self, pat, txt):
		m = {}
		for i in pat:
			m[i] = m.get(i, 0) + 1
		k = len(pat)
		count = len(m)
		ans = 0
		(i, j) = (0, 0)
		while j < len(txt):
			if txt[j] in m:
				m[txt[j]] -= 1
				if m[txt[j]] == 0:
					count -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if count == 0:
					ans += 1
				if txt[i] in m:
					m[txt[i]] += 1
					if m[txt[i]] == 1:
						count += 1
				i += 1
				j += 1
		return ans


class Solution:

	def search(self, pat, txt):
		k = len(pat)
		n = len(txt)
		map = {}
		for i in range(k):
			if pat[i] not in map:
				map[pat[i]] = 1
			else:
				map[pat[i]] += 1
		i = 0
		j = 0
		txt_map = {}
		count = 0
		while j < n:
			if txt[j] not in txt_map:
				txt_map[txt[j]] = 1
			else:
				txt_map[txt[j]] += 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if map == txt_map:
					count += 1
				txt_map[txt[i]] -= 1
				if txt_map[txt[i]] == 0:
					del txt_map[txt[i]]
				i += 1
				j += 1
		return count


class Solution:

	def search(self, pat, txt):
		re = len(pat)
		now = 0
		dic = {}
		lp = len(pat)
		ans = 0
		for i in pat:
			if dic.get(i, -1) == -1:
				dic[i] = [1, 0]
			else:
				dic[i][0] += 1
		i = 0
		while i < len(txt):
			if i < lp - 1:
				if dic.get(txt[i], -1) != -1:
					dic[txt[i]][1] += 1
					if dic[txt[i]][0] >= dic[txt[i]][1]:
						now += 1
			else:
				if dic.get(txt[i], -1) != -1:
					dic[txt[i]][1] += 1
					if dic[txt[i]][0] >= dic[txt[i]][1]:
						now += 1
				if now == re:
					ans += 1
				if dic.get(txt[i - (lp - 1)], -1) != -1:
					dic[txt[i - (lp - 1)]][1] -= 1
					if dic[txt[i - (lp - 1)]][0] > dic[txt[i - (lp - 1)]][1]:
						now -= 1
			i += 1
		return ans


class Solution:

	def search(self, pat, txt):
		pat_hash_sum = sum([ord(c) for c in pat])
		sorted_pat = ''.join(sorted(pat))
		txt_len = len(txt)
		pat_len = len(pat)
		txt_hash_map = {i: v for (i, v) in enumerate(txt)}
		count = 0
		hash_sum = sum([ord(txt_hash_map[i]) for i in range(pat_len)])
		if pat_hash_sum == hash_sum:
			sorted_temp = ''.join(sorted(txt[:pat_len]))
			if sorted_temp == sorted_pat:
				count += 1
		i = pat_len - 1
		while i < txt_len - 1:
			i += 1
			hash_sum += ord(txt_hash_map[i])
			hash_sum -= ord(txt_hash_map[i - pat_len])
			if pat_hash_sum == hash_sum:
				sorted_temp = ''.join(sorted(txt[i - pat_len + 1:i + 1]))
				if sorted_temp == sorted_pat:
					count += 1
		return count


class Solution:
	MAX = 256

	def compare(self, arr1, arr2):
		for i in range(self.MAX):
			if arr1[i] != arr2[i]:
				return False
		return True

	def search(self, pat, txt):
		txt_len = len(txt)
		pat_len = len(pat)
		pat_list = [0] * self.MAX
		txt_list = [0] * self.MAX
		for i in range(pat_len):
			pat_list[ord(pat[i])] += 1
			txt_list[ord(txt[i])] += 1
		count = 0
		if self.compare(pat_list, txt_list):
			count += 1
		for i in range(pat_len, txt_len):
			txt_list[ord(txt[i])] += 1
			txt_list[ord(txt[i - pat_len])] -= 1
			if self.compare(pat_list, txt_list):
				count += 1
		return count


import collections

class Solution:

	def search(self, pat, txt):
		n = len(txt)
		k = len(pat)
		hm = {}
		for i in range(len(pat)):
			if pat[i] in hm:
				hm[pat[i]] += 1
			else:
				hm[pat[i]] = 1
		count = len(hm)
		(i, j) = (0, 0)
		ans = 0
		while j < n:
			if txt[j] in hm:
				hm[txt[j]] -= 1
				if hm[txt[j]] == 0:
					count -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if count == 0:
					ans += 1
				if txt[i] in hm:
					hm[txt[i]] += 1
					if hm[txt[i]] == 1:
						count += 1
				i += 1
				j += 1
		return ans


class Solution:

	def search(self, pat, txt):
		p = {}
		for i in pat:
			c = p.get(i, 0)
			p.update({i: c + 1})
		c = len(p)
		k = len(pat)
		i = 0
		j = 0
		d = {}
		o = 0
		while j < len(txt):
			if txt[j] in p:
				p[txt[j]] -= 1
				if p[txt[j]] == 0:
					c = c - 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if c == 0:
					o += 1
				if txt[i] in p:
					if p[txt[i]] == 0:
						c += 1
					p[txt[i]] += 1
				i += 1
				j += 1
		return o


from collections import Counter

class Solution:

	def search(self, pat, txt):
		i = 0
		j = 0
		count = 0
		pattdictionary = Counter(pat)
		dicLength = len(pattdictionary)
		k = len(pat)
		while j < len(txt):
			if txt[j] in pattdictionary:
				pattdictionary[txt[j]] -= 1
				if pattdictionary[txt[j]] == 0:
					dicLength -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if dicLength == 0:
					count += 1
				if txt[i] in pattdictionary:
					pattdictionary[txt[i]] += 1
					if pattdictionary[txt[i]] == 1:
						dicLength += 1
				i += 1
				j += 1
		return count


class Solution:

	def search(self, pat, txt):
		count = 0
		startingIndex = 0
		mapX = {}
		for k in range(len(pat)):
			mapX[pat[k]] = mapX.get(pat[k], 0) + 1
		tempMap = {}
		for j in range(len(pat)):
			tempMap[txt[j]] = tempMap.get(txt[j], 0) + 1
		if mapX == tempMap:
			count += 1
		for i in range(len(pat), len(txt)):
			tempMap[txt[i]] = tempMap.get(txt[i], 0) + 1
			tempMap[txt[startingIndex]] -= 1
			if tempMap[txt[startingIndex]] == 0:
				del tempMap[txt[startingIndex]]
			startingIndex += 1
			if mapX == tempMap:
				count += 1
		return count


class Solution:

	def search(self, pat, txt):
		n = len(txt)
		m = len(pat)
		countP = [0] * 26
		countTW = [0] * 26
		for i in range(m):
			countP[ord(pat[i]) - 97] += 1
			countTW[ord(txt[i]) - 97] += 1
		count = 0
		for i in range(m, n):
			if countP == countTW:
				count += 1
			countTW[ord(txt[i - m]) - 97] -= 1
			countTW[ord(txt[i]) - 97] += 1
		if countP == countTW:
			count += 1
		return count


from collections import Counter
from collections import defaultdict

class Solution:

	def search(self, pat, txt):
		d1 = Counter(pat)
		k = len(pat)
		(i, j) = (0, 0)
		c = 0
		d = defaultdict(int)
		for j in range(len(txt)):
			d[txt[j]] += 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if d == d1:
					c += 1
				d[txt[i]] -= 1
				if d[txt[i]] == 0:
					del d[txt[i]]
				i += 1
				j += 1
		return c


class Solution:

	def search(self, pat, txt):
		dic1 = {}
		for i in pat:
			dic1[i] = dic1.get(i, 0) + 1

		def check(dic1, dic2):
			if len(dic1) != len(dic2):
				return False
			for i in dic1:
				if i not in dic2 or dic1[i] != dic2[i]:
					return False
			return True
		i = 0
		j = 0
		dic2 = {}
		ans = 0
		while j < len(txt):
			if j - i < len(pat):
				dic2[txt[j]] = dic2.get(txt[j], 0) + 1
				j += 1
			else:
				dic2[txt[j]] = dic2.get(txt[j], 0) + 1
				dic2[txt[i]] -= 1
				if dic2[txt[i]] == 0:
					del dic2[txt[i]]
				i += 1
				j += 1
			if check(dic1, dic2):
				ans += 1
		return ans


import collections

class Solution:

	def search(self, pat, txt):
		count = 0
		k = len(pat)
		patHashMap = collections.defaultdict(int)
		for l in pat:
			patHashMap[l] += 1
		hashMap = collections.defaultdict(int)
		(i, j) = (0, 0)
		while j < len(txt):
			hashMap[txt[j]] += 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if patHashMap == hashMap:
					count += 1
				hashMap[txt[i]] -= 1
				if hashMap[txt[i]] == 0:
					hashMap.pop(txt[i])
				i += 1
				j += 1
		return count


class Solution:

	def search(self, s2, s1):
		k = len(s2)
		(count, res) = (0, 0)
		d = {}
		for i in s2:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		(i, j) = (0, 0)
		count = len(d)
		while j < len(s1):
			if s1[j] in d.keys():
				d[s1[j]] -= 1
				if d[s1[j]] == 0:
					count -= 1
			if j - i + 1 < k:
				j += 1
			else:
				if count == 0:
					res += 1
				if s1[i] in d:
					d[s1[i]] += 1
					if d[s1[i]] == 1:
						count += 1
				i += 1
				j += 1
		return res


class Solution:

	def search(self, pat, txt):
		d = {}
		d_ = {}
		c = 0
		ans = 0
		for i in pat:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in range(len(pat)):
			if txt[i] in d.keys():
				if txt[i] not in d_.keys():
					d_[txt[i]] = 1
				else:
					d_[txt[i]] += 1
				if d_[txt[i]] == d[txt[i]]:
					c += 1
				elif d_[txt[i]] - d[txt[i]] == 1:
					c -= 1
				if c == len(d):
					ans += 1
		i = len(pat)
		while i < len(txt):
			if txt[i] in d.keys() and txt[i - len(pat)] not in d.keys():
				if txt[i] not in d_.keys():
					d_[txt[i]] = 1
				else:
					d_[txt[i]] += 1
				if d_[txt[i]] == d[txt[i]]:
					c += 1
				elif d_[txt[i]] - d[txt[i]] == 1:
					c -= 1
				if c == len(d):
					ans += 1
			elif txt[i] not in d.keys() and txt[i - len(pat)] in d.keys():
				d_[txt[i - len(pat)]] -= 1
				if d[txt[i - len(pat)]] - d_[txt[i - len(pat)]] == 1:
					c -= 1
				elif d_[txt[i - len(pat)]] == d[txt[i - len(pat)]]:
					c += 1
			elif txt[i] in d.keys() and txt[i - len(pat)] in d.keys():
				if txt[i] == txt[i - len(pat)]:
					if c == len(d):
						ans += 1
				else:
					if txt[i] not in d_.keys():
						d_[txt[i]] = 1
					else:
						d_[txt[i]] += 1
					d_[txt[i - len(pat)]] -= 1
					if d_[txt[i]] == d[txt[i]]:
						c += 1
					elif d_[txt[i]] - d[txt[i]] == 1:
						c -= 1
					if d[txt[i - len(pat)]] - d_[txt[i - len(pat)]] == 1:
						c -= 1
					elif d_[txt[i - len(pat)]] == d[txt[i - len(pat)]]:
						c += 1
					if c == len(d):
						ans += 1
			i += 1
		return ans


class Solution:

	def search(self, pat, txt):
		pat_map = {}
		for ch in pat:
			pat_map[ch] = pat_map.get(ch, 0) + 1
		k = len(pat)
		(i, j) = (0, 0)
		count = 0
		check_map = {}
		while j < len(txt):
			if txt[j] in pat_map:
				check_map[txt[j]] = check_map.get(txt[j], 0) + 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if check_map == pat_map:
					count += 1
				if txt[i] in check_map:
					check_map[txt[i]] -= 1
				i += 1
				j += 1
		return count


class Solution:

	def search(self, pat, txt):
		pat_map = {}
		for ch in pat:
			pat_map[ch] = pat_map.get(ch, 0) + 1
		K = len(pat)
		i = 0
		j = 0
		ans = 0
		check_map = {}
		while j < len(txt):
			if txt[j] in pat_map:
				check_map[txt[j]] = check_map.get(txt[j], 0) + 1
			if j - i + 1 < K:
				j += 1
			elif j - i + 1 == K:
				if check_map == pat_map:
					ans += 1
				if txt[i] in check_map:
					check_map[txt[i]] -= 1
				i += 1
				j += 1
		return ans


class Solution:

	def search(self, pat, txt):
		freq = {}
		for char in pat:
			if char in freq:
				freq[char] += 1
			else:
				freq[char] = 1
		r = l = 0
		n = len(txt)
		count = len(freq)
		k = len(pat)
		ans = 0
		while r < n:
			if txt[r] in freq:
				freq[txt[r]] -= 1
				if freq[txt[r]] == 0:
					count -= 1
			if r - l + 1 < k:
				r += 1
			elif r - l + 1 == k:
				if count == 0:
					ans += 1
				if txt[l] in freq:
					freq[txt[l]] += 1
					if freq[txt[l]] == 1:
						count += 1
				r += 1
				l += 1
		return ans


class Solution:

	def search(self, pat, txt):
		patFreq = {chr(k): 0 for k in range(ord('a'), ord('z') + 1)}
		txtFreq = {chr(k): 0 for k in range(ord('a'), ord('z') + 1)}
		count = 0
		for c in pat:
			patFreq[c] += 1
		for i in range(len(pat)):
			txtFreq[txt[i]] += 1
		for i in range(len(pat), len(txt)):
			if txtFreq == patFreq:
				count += 1
			txtFreq[txt[i - len(pat)]] -= 1
			txtFreq[txt[i]] += 1
		if txtFreq == patFreq:
			count += 1
		return count


def getValue(character):
	return ord(character) - ord('a')

class Solution:

	def search(self, pat, text):
		patternCount = [0 for _ in range(26)]
		textCount = [0 for _ in range(26)]
		index = 0
		length = len(pat)
		occurences = 0
		while index < length:
			patternCount[getValue(pat[index])] += 1
			textCount[getValue(text[index])] += 1
			index += 1
		if patternCount == textCount:
			occurences += 1
		index = 0
		while index + length < len(text):
			textCount[getValue(text[index])] -= 1
			textCount[getValue(text[index + length])] += 1
			if patternCount == textCount:
				occurences += 1
			index += 1
		return occurences


class Solution:

	def search(self, pat, txt):
		d = {}
		ans = 0
		for ch in pat:
			d[ch] = d.get(ch, 0) + 1
		i = 0
		j = 0
		n = len(txt)
		k = len(pat)
		temp = {}
		while j < n:
			temp[txt[j]] = temp.get(txt[j], 0) + 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if temp == d:
					ans += 1
				temp[txt[i]] = temp[txt[i]] - 1
				if temp[txt[i]] == 0:
					temp.pop(txt[i])
				i += 1
				j += 1
		return ans


from collections import Counter

class Solution:

	def search(self, pat, txt):
		(m, n) = (len(pat), len(txt))
		count1 = Counter(pat)
		count2 = Counter(txt[:m])
		ans = 0
		for i in range(n - m + 1):
			if count1 == count2:
				ans += 1
			count2[txt[i]] -= 1
			if count2[txt[i]] == 0:
				del count2[txt[i]]
			if i + m < n:
				count2[txt[i + m]] += 1
		return ans


class Solution:

	def search(self, pat, txt):
		answer = 0
		freqS = [0] * 26
		for c in pat:
			freqS[ord(c) - 97] += 1
		freqArr = [0] * 26
		for i in range(len(pat)):
			freqArr[ord(txt[i]) - 97] += 1
		if freqArr == freqS:
			answer += 1
		for i in range(len(pat), len(txt)):
			freqArr[ord(txt[i - len(pat)]) - 97] -= 1
			freqArr[ord(txt[i]) - 97] += 1
			if freqArr == freqS:
				answer += 1
		return answer


class Solution:

	def search(self, pat, txt):
		(patDict, txtDict) = ({}, {})
		for i in pat:
			if i not in patDict:
				patDict[i] = 1
			else:
				patDict[i] += 1
		(i, j) = (0, 0)
		count = 0
		while j < len(txt):
			if txt[j] not in txtDict:
				txtDict[txt[j]] = 1
			else:
				txtDict[txt[j]] += 1
			if j - i + 1 == len(pat):
				if txtDict == patDict:
					count += 1
			elif j - i + 1 > len(pat):
				if txtDict[txt[i]] > 1:
					txtDict[txt[i]] -= 1
				else:
					del txtDict[txt[i]]
				i += 1
				if j - i + 1 == len(pat) and txtDict == patDict:
					count += 1
			j += 1
		return count


from collections import Counter

class Solution:

	def search(self, pat, txt):
		counter = Counter(pat)
		count = len(counter)
		(ans, i, j) = (0, 0, 0)
		k = len(pat)
		while j < len(txt):
			if txt[j] in counter:
				counter[txt[j]] -= 1
				if counter[txt[j]] == 0:
					count -= 1
			if j - i + 1 == k:
				if count == 0:
					ans += 1
				if txt[i] in counter:
					if counter[txt[i]] == 0:
						count += 1
					counter[txt[i]] += 1
				i += 1
			j += 1
		return ans


class Solution:

	def search(self, pat, txt):
		wHeap = [0] * 26
		textHeap = [0] * 26
		start = 0
		count = 0
		for c in pat:
			wHeap[ord(c) - ord('a')] += 1
		for i in range(len(txt)):
			textHeap[ord(txt[i]) - ord('a')] += 1
			if i - start + 1 == len(pat):
				if textHeap == wHeap:
					count += 1
				textHeap[ord(txt[start]) - ord('a')] -= 1
				start += 1
		return count


class Solution:

	def search(self, pat, txt):
		pcount = {}
		scount = {}
		ans = 0
		if len(txt) < len(pat):
			return ans
		for i in range(0, len(pat)):
			s = pat[i]
			g = txt[i]
			if s not in pcount:
				pcount[s] = 1
			else:
				pcount[s] = pcount[s] + 1
			if g not in scount:
				scount[g] = 1
			else:
				scount[g] = scount[g] + 1
		if scount == pcount:
			ans = 1
		l = 0
		for r in range(len(pat), len(txt)):
			g = txt[r]
			if g not in scount:
				scount[g] = 1
			else:
				scount[g] = scount[g] + 1
			m = txt[l]
			scount[m] = scount[m] - 1
			if scount[m] == 0:
				scount.pop(m)
			l = l + 1
			if scount == pcount:
				ans = ans + 1
		return ans


class Solution:

	def search(self, pat, txt):
		mp = {}
		for a in pat:
			if a not in mp:
				mp[a] = 0
			mp[a] += 1
		count = len(mp)
		(i, j, k, n, ans) = (0, 0, len(pat), len(txt), 0)
		while j < n:
			if txt[j] in mp:
				mp[txt[j]] -= 1
				if mp[txt[j]] == 0:
					count -= 1
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if count == 0:
					ans += 1
				if txt[i] in mp:
					mp[txt[i]] += 1
					if mp[txt[i]] == 1:
						count += 1
				i += 1
				j += 1
		return ans