Given two strings S and P. Find the smallest window in the string S consisting of all the characters(including duplicates) of the string P.  Return "-1" in case there is no such window present. In case there are multiple such windows of same length, return the one with the least starting index.
Note : All characters are in Lowercase alphabets. 
Example 1:
Input:
S = "timetopractice"
P = "toc"
Output: 
toprac
Explanation: "toprac" is the smallest
substring in which "toc" can be found.
Example 2:
Input:
S = "zoomlazapzo"
P = "oza"
Output: 
apzo
Explanation: "apzo" is the smallest 
substring in which "oza" can be found.
Your Task:
You don't need to read input or print anything. Your task is to complete the function smallestWindow() which takes two string S and P as input paramters and returns the smallest window in string S having all the characters of the string P. In case there are multiple such windows of same length, return the one with the least starting index. 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(n) n = len(p) O
Constraints: 
1 ≤ |S|, |P| ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Dynamic programming

Amortized analysis

Starter code: #User function Template for python3





class Solution:

    

    #Function to find the smallest window in the string s consisting

    #of all the characters of string p.

    def smallestWindow(self, s, p):

        #code here

Solutions:
class Solution:

	def smallestWindow(self, s, p):
		res = ''
		ans = len(s)
		dic = {}
		for i in p:
			if i in dic:
				dic[i] = dic[i] + 1
			else:
				dic[i] = 1
		count = len(dic)
		i = 0
		start = 0
		j = 0
		while j < len(s):
			if s[j] in dic:
				dic[s[j]] = dic[s[j]] - 1
			else:
				dic[s[j]] = -1
			if dic[s[j]] == 0:
				count = count - 1
			if count == 0:
				while count == 0:
					if ans > j - i + 1:
						ans = j - i + 1
						start = i
					if s[i] in dic:
						dic[s[i]] = dic[s[i]] + 1
					if dic[s[i]] > 0:
						count = count + 1
					i = i + 1
			j = j + 1
		if ans == len(s):
			return '-1'
		else:
			return s[start:start + ans]


class Solution:

	def smallestWindow(self, s, p):
		if len(s) < len(p):
			return '-1'
		hash_pat = [0] * 256
		hash_str = [0] * 256
		for i in range(len(p)):
			hash_pat[ord(p[i])] += 1
		(start, start_index, min_len) = (0, -1, float('inf'))
		count = 0
		for j in range(len(s)):
			hash_str[ord(s[j])] += 1
			if hash_pat[ord(s[j])] != 0 and hash_str[ord(s[j])] <= hash_pat[ord(s[j])]:
				count += 1
			if count == len(p):
				while hash_str[ord(s[start])] > hash_pat[ord(s[start])] or hash_pat[ord(s[start])] == 0:
					if hash_str[ord(s[start])] > hash_pat[ord(s[start])]:
						hash_str[ord(s[start])] -= 1
					start += 1
				len_window = j - start + 1
				if min_len > len_window:
					min_len = len_window
					start_index = start
		if start_index == -1:
			return '-1'
		return s[start_index:start_index + min_len]


class Solution:

	def smallestWindow(self, s, p):
		if len(s) < len(p):
			return -1
		d1 = {}
		d2 = {}
		for i in p:
			if i in d1:
				d1[i] += 1
			else:
				d1[i] = 1
		count = 0
		start = 0
		l = 9999999999999
		ans = ''
		for i in range(len(s)):
			if s[i] in d2:
				d2[s[i]] += 1
			else:
				d2[s[i]] = 1
			if s[i] in p and d2[s[i]] == d1[s[i]]:
				count += 1
			if count == len(d1):
				if l > len(s[start:i + 1]):
					ans = s[start:i + 1]
					l = len(s[start:i + 1])
				while start < i:
					if d2[s[start]] != 0:
						d2[s[start]] -= 1
					if s[start] in d1 and d2[s[start]] == d1[s[start]]:
						start += 1
						if l > len(s[start:i + 1]):
							ans = s[start:i + 1]
							l = len(s[start:i + 1])
					elif s[start] in d1 and d2[s[start]] < d1[s[start]]:
						if l > len(s[start:i + 1]):
							ans = s[start:i + 1]
							l = len(s[start:i + 1])
						start += 1
						count -= 1
						break
					else:
						start += 1
		if ans == '':
			return -1
		return ans


class Solution:

	def smallestWindow(self, s, p):
		if p == '':
			return -1
		(countT, window) = ({}, {})
		for c in p:
			countT[c] = 1 + countT.get(c, 0)
		l = 0
		(have, need) = (0, len(countT))
		(res, resLen) = ([-1, -1], float('inf'))
		for r in range(len(s)):
			c = s[r]
			window[c] = 1 + window.get(c, 0)
			if c in countT and window[c] == countT[c]:
				have += 1
			while have == need:
				if r - l + 1 < resLen:
					res = [l, r]
					resLen = r - l + 1
				window[s[l]] -= 1
				if s[l] in countT and window[s[l]] < countT[s[l]]:
					have -= 1
				l += 1
		(l, r) = res
		return s[l:r + 1] if resLen != float('inf') else -1


class Solution:

	def smallestWindow(self, s, p):
		p_count = {}
		for i in p:
			p_count[i] = p_count.get(i, 0) + 1
		s_count = {}
		counter = 0
		min_window = float('inf')
		start_index = 0
		(left, right) = (0, 0)
		while right < len(s):
			s_count[s[right]] = s_count.get(s[right], 0) + 1
			if s[right] in p_count and s_count[s[right]] <= p_count[s[right]]:
				counter += 1
			while counter == len(p):
				if right - left + 1 < min_window:
					min_window = right - left + 1
					start_index = left
				s_count[s[left]] -= 1
				if s[left] in p_count and s_count[s[left]] < p_count[s[left]]:
					counter -= 1
				left += 1
			right += 1
		return s[start_index:start_index + min_window] if min_window != float('inf') else '-1'


class Solution:

	def smallestWindow(self, s, p):
		no_of_chars = 256
		len1 = len(s)
		len2 = len(p)
		if len1 < len2:
			return -1
		hash_p = [0] * no_of_chars
		hash_str = [0] * no_of_chars
		for i in range(0, len2):
			hash_p[ord(p[i])] += 1
		(start, start_index, min_len) = (0, -1, float('inf'))
		count = 0
		for j in range(0, len1):
			hash_str[ord(s[j])] += 1
			if hash_str[ord(s[j])] <= hash_p[ord(s[j])]:
				count += 1
			if count == len2:
				while hash_str[ord(s[start])] > hash_p[ord(s[start])] or hash_p[ord(s[start])] == 0:
					if hash_str[ord(s[start])] > hash_p[ord(s[start])]:
						hash_str[ord(s[start])] -= 1
					start += 1
				len_window = j - start + 1
				if min_len > len_window:
					min_len = len_window
					start_index = start
		if start_index == -1:
			return -1
		return s[start_index:start_index + min_len]


class Solution:

	def smallestWindow(self, S, P):
		count_p = [0] * 26
		count_s = [0] * 26
		for char in P:
			count_p[ord(char) - ord('a')] += 1
		window_start = 0
		window_end = 0
		min_window_size = float('inf')
		min_window_start = 0
		matched = 0
		while window_end < len(S):
			count_s[ord(S[window_end]) - ord('a')] += 1
			if count_s[ord(S[window_end]) - ord('a')] <= count_p[ord(S[window_end]) - ord('a')]:
				matched += 1
			if matched == len(P):
				while count_s[ord(S[window_start]) - ord('a')] > count_p[ord(S[window_start]) - ord('a')]:
					count_s[ord(S[window_start]) - ord('a')] -= 1
					window_start += 1
				current_window_size = window_end - window_start + 1
				if current_window_size < min_window_size:
					min_window_size = current_window_size
					min_window_start = window_start
			window_end += 1
		if min_window_size == float('inf'):
			return '-1'
		return S[min_window_start:min_window_start + min_window_size]


class Solution:

	def smallestWindow(self, s, p):
		if p == '':
			return ''
		reslen = float('inf')
		need = {}
		for i in p:
			need[i] = 1 + need.get(i, 0)
		needCount = len(need)
		window = {}
		haveCount = 0
		res = [-1, -1]
		l = 0
		for r in range(len(s)):
			window[s[r]] = 1 + window.get(s[r], 0)
			if s[r] in need and window[s[r]] == need[s[r]]:
				haveCount += 1
			while haveCount == needCount:
				if r - l + 1 < reslen:
					res = [l, r]
					reslen = r - l + 1
				window[s[l]] -= 1
				if s[l] in need and window[s[l]] < need[s[l]]:
					haveCount -= 1
				l += 1
		(l, r) = res
		return s[l:r + 1] if reslen != float('inf') else -1


class Solution:

	def smallestWindow(self, s, p):
		n = len(s)
		D = {}
		var = '-1'
		for k in p:
			if k in D:
				D[k] += 1
			else:
				D[k] = 1
		(i, j) = (0, 0)
		count = len(D)
		mini = 9999
		while j < n:
			if s[j] in D:
				D[s[j]] -= 1
				if D[s[j]] == 0:
					count -= 1
			while count == 0:
				if j - i + 1 < mini:
					mini = j - i + 1
					var = s[i:j + 1]
				if s[i] in D:
					D[s[i]] += 1
					if D[s[i]] > 0:
						count += 1
				i += 1
			j += 1
		return var


class Solution:

	def smallestWindow(self, s, p):
		if len(p) > len(s):
			return -1
		shash = [0 for i in range(26)]
		phash = [0 for i in range(26)]
		for char in p:
			phash[ord(char) - ord('a')] += 1
		counter = 0
		begin = 0
		startindex = -1
		length = 0
		minlength = 10000000000.0
		for i in range(len(s)):
			shash[ord(s[i]) - ord('a')] += 1
			if phash[ord(s[i]) - ord('a')] != 0 and shash[ord(s[i]) - ord('a')] <= phash[ord(s[i]) - ord('a')]:
				counter += 1
			if counter == len(p):
				while shash[ord(s[begin]) - ord('a')] > phash[ord(s[begin]) - ord('a')] or phash[ord(s[begin]) - ord('a')] == 0:
					if shash[ord(s[begin]) - ord('a')] > phash[ord(s[begin]) - ord('a')]:
						shash[ord(s[begin]) - ord('a')] -= 1
						begin += 1
				length = i - begin + 1
				if length < minlength:
					startindex = begin
					minlength = length
		if startindex == -1:
			return '-1'
		else:
			return s[startindex:startindex + minlength]


class Solution:

	def smallestWindow(self, s, p):
		n = len(s)
		m = len(p)
		if m > n:
			return '-1'
		sFreq = [0] * 26
		pFreq = [0] * 26
		for i in range(m):
			pFreq[ord(p[i]) - ord('a')] += 1
		start = 0
		end = 0
		count = 0
		minLength = float('inf')
		startIndex = -1
		while end < n:
			sFreq[ord(s[end]) - ord('a')] += 1
			if sFreq[ord(s[end]) - ord('a')] <= pFreq[ord(s[end]) - ord('a')]:
				count += 1
			if count == m:
				while sFreq[ord(s[start]) - ord('a')] > pFreq[ord(s[start]) - ord('a')] or pFreq[ord(s[start]) - ord('a')] == 0:
					sFreq[ord(s[start]) - ord('a')] -= 1
					start += 1
				windowLength = end - start + 1
				if windowLength < minLength:
					minLength = windowLength
					startIndex = start
			end += 1
		if startIndex == -1:
			return '-1'
		else:
			return s[startIndex:startIndex + minLength]


class Solution:

	def smallestWindow(self, s, p):
		(i, ans, string) = (0, float('inf'), '')
		d = {}

		def check(d):
			for key in d:
				if d[key] > 0:
					return False
			return True
		for k in range(len(p)):
			d[p[k]] = 1 + d.get(p[k], 0)
		for j in range(len(s)):
			if s[j] in d:
				d[s[j]] -= 1
			while i <= j and check(d):
				if s[i] in d:
					d[s[i]] += 1
				if j - i + 1 < ans:
					ans = min(ans, j - i + 1)
					string = s[i:j + 1]
				i += 1
		return string if string else -1


class Solution:

	def smallestWindow(self, s, p):
		Ans = len(s)
		Dict = {}
		for i in p:
			if i in Dict:
				Dict[i] = Dict[i] + 1
			else:
				Dict[i] = 1
		count = len(Dict)
		i = 0
		start = 0
		j = 0
		while j < len(s):
			if s[j] in Dict:
				Dict[s[j]] = Dict[s[j]] - 1
			else:
				Dict[s[j]] = -1
			if Dict[s[j]] == 0:
				count = count - 1
			if count == 0:
				while count == 0:
					if Ans > j - i + 1:
						Ans = j - i + 1
						start = i
					if s[i] in Dict:
						Dict[s[i]] = Dict[s[i]] + 1
					if Dict[s[i]] > 0:
						count = count + 1
					i = i + 1
			j = j + 1
		if Ans == len(s):
			return '-1'
		else:
			return s[start:start + Ans]


class Solution:

	def smallestWindow(self, s, p):
		d = {}
		for i in p:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		cd = 0
		for i in d:
			cd = cd + d[i]
		km = d
		i = j = 0
		c = 0
		minm = 9999
		minmd = []
		while j < len(s) or c == cd:
			if c != cd:
				if s[j] in d:
					if d[s[j]] > 0:
						c = c + 1
					d[s[j]] = d[s[j]] - 1
				j = j + 1
			else:
				if j - i < minm:
					minm = j - i
					minmd.append(s[i:j])
				if s[i] in d:
					if d[s[i]] <= 0:
						d[s[i]] += 1
					if d[s[i]] > 0:
						c = c - 1
				i = i + 1
		if len(minmd) == 0:
			return -1
		return minmd[len(minmd) - 1]


class Solution:

	def smallestWindow(self, s, p):
		n = len(s)
		if len(s) < len(p):
			return '-1'
		ch = [0] * 256
		ct = 0
		start = 0
		ans = n + 1
		for i in range(len(p)):
			ch[ord(p[i])] += 1
			if ch[ord(p[i])] == 1:
				ct += 1
		(i, j) = (0, 0)
		while j < n:
			ch[ord(s[j])] -= 1
			if ch[ord(s[j])] == 0:
				ct -= 1
				while ct == 0:
					if ans > j - i + 1:
						ans = j - i + 1
						start = i
					ch[ord(s[i])] += 1
					if ch[ord(s[i])] > 0:
						ct += 1
					i += 1
			j += 1
		if ans > n:
			return '-1'
		return s[start:start + ans]


from collections import Counter

class Solution:

	def smallestWindow(self, S, P):
		p_count = Counter(P)
		s_count = Counter()
		(left, right) = (0, 0)
		count = len(p_count)
		ans = (float('inf'), None, None)
		while right < len(S):
			s_count[S[right]] += 1
			if S[right] in p_count and s_count[S[right]] == p_count[S[right]]:
				count -= 1
			while count == 0:
				if right - left < ans[0]:
					ans = (right - left, left, right)
				s_count[S[left]] -= 1
				if S[left] in p_count and s_count[S[left]] < p_count[S[left]]:
					count += 1
				left += 1
			right += 1
		return '-1' if ans[0] == float('inf') else S[ans[1]:ans[2] + 1]


class Solution:

	def smallestWindow(self, s, p):
		start = 0
		end = 0
		freq = [0] * 26
		n = len(s)
		size = 0
		st = set(p)
		m = len(st)
		freq_target = [0] * 26
		for i in p:
			freq_target[ord(i) - ord('a')] += 1
		min_size = 9999999
		ans = [-1, -1]
		curr = 0
		while end < n and start <= end:
			if s[end] in st:
				index = ord(s[end]) - ord('a')
				freq[index] += 1
				if freq[index] == freq_target[index]:
					size += 1
			curr += 1
			while size == m:
				if curr < min_size:
					min_size = curr
					ans = [start, end]
				if s[start] in st:
					index = ord(s[start]) - ord('a')
					freq[index] -= 1
					if freq[index] < freq_target[index]:
						size -= 1
				start += 1
				curr -= 1
			end += 1
		if ans == [-1, -1]:
			return -1
		else:
			(i, j) = ans
			return s[i:j + 1]


class Solution:

	def smallestWindow(self, s, p):
		p_counter = [0] * 256
		s_counter = [0] * 256
		for c in p:
			p_counter[ord(c)] += 1
		left = 0
		min_len = float('inf')
		min_substr = ''
		required_chars = len(p)
		for (right, char) in enumerate(s):
			if p_counter[ord(char)] > 0:
				s_counter[ord(char)] += 1
				if s_counter[ord(char)] <= p_counter[ord(char)]:
					required_chars -= 1
			while required_chars == 0:
				if right - left + 1 < min_len:
					min_len = right - left + 1
					min_substr = s[left:right + 1]
				if p_counter[ord(s[left])] > 0:
					s_counter[ord(s[left])] -= 1
					if s_counter[ord(s[left])] < p_counter[ord(s[left])]:
						required_chars += 1
				left += 1
		return min_substr if min_substr else '-1'


class Solution:

	def smallestWindow(self, s, p):
		n = len(s)
		if n < len(p):
			return -1
		m = [0] * 256
		start = 0
		ans = n + 1
		cnt = 0
		for i in p:
			m[ord(i)] += 1
			if m[ord(i)] == 1:
				cnt += 1
		i = 0
		j = 0
		while j < n:
			m[ord(s[j])] -= 1
			if m[ord(s[j])] == 0:
				cnt -= 1
			while cnt == 0:
				if ans > j - i + 1:
					ans = j - i + 1
					start = i
				m[ord(s[i])] += 1
				if m[ord(s[i])] > 0:
					cnt += 1
				i += 1
			j += 1
		if ans > n:
			return -1
		return s[start:start + ans]


from collections import Counter, defaultdict

class Solution:

	def smallestWindow(self, s, p):
		(res, x) = (s, {})
		for i in p:
			if i in x:
				x[i] += 1
			else:
				x[i] = 1
		(c, i, j) = (0, 0, 0)
		y = {}
		while j < len(s):
			if s[j] in y:
				y[s[j]] += 1
			else:
				y[s[j]] = 1
			if s[j] in x:
				if x[s[j]] >= y[s[j]]:
					c += 1
			if c == len(p):
				while 1:
					if s[i] not in x:
						i += 1
					elif y[s[i]] > x[s[i]]:
						y[s[i]] -= 1
						i += 1
					else:
						break
				if len(s[i:j + 1]) < len(res):
					res = s[i:j + 1]
			j += 1
		if res == s:
			return -1
		return res


class Solution:

	def smallestWindow(self, s, p):
		n = len(s)
		dict_p = {}
		count = len(set(p))
		ans = n
		res = s
		for i in p:
			if i in dict_p:
				dict_p[i] += 1
			else:
				dict_p[i] = 1
		i = j = 0
		while j < n:
			if s[j] in dict_p:
				dict_p[s[j]] -= 1
				if dict_p[s[j]] == 0:
					count -= 1
			while count == 0:
				if ans > j - i + 1:
					ans = j - i + 1
					res = s[i:j + 1]
				if s[i] in dict_p:
					dict_p[s[i]] += 1
					if dict_p[s[i]] == 1:
						count += 1
				i += 1
			if count > 0:
				j += 1
		if ans == n:
			return '-1'
		return res


from collections import defaultdict, Counter

class Solution:

	def smallestWindow(self, s, p):
		res = ''
		ans = len(s)
		dic = {}
		for i in p:
			if i in dic:
				dic[i] = dic[i] + 1
			else:
				dic[i] = 1
		count = len(dic)
		i = 0
		start = 0
		j = 0
		while j < len(s):
			if s[j] in dic:
				dic[s[j]] = dic[s[j]] - 1
			else:
				dic[s[j]] = -1
			if dic[s[j]] == 0:
				count = count - 1
			if count == 0:
				while count == 0:
					if ans > j - i + 1:
						ans = j - i + 1
						start = i
					if s[i] in dic:
						dic[s[i]] = dic[s[i]] + 1
					if dic[s[i]] > 0:
						count = count + 1
					i = i + 1
			j = j + 1
		if ans == len(s):
			return '-1'
		else:
			return s[start:start + ans]


class Solution:

	def smallestWindow(self, s, t):
		if t == '':
			return ''
		(countT, window) = ({}, {})
		have = 0
		for c in t:
			countT[c] = 1 + countT.get(c, 0)
		need = len(countT)
		res = [-1, -1]
		resLen = float('infinity')
		l = 0
		for r in range(len(s)):
			c = s[r]
			window[c] = 1 + window.get(c, 0)
			if c in countT and window[c] == countT[c]:
				have += 1
			while have == need:
				if r - l - 1 < resLen:
					resLen = r - l - 1
					res = [l, r]
				window[s[l]] -= 1
				if s[l] in countT and window[s[l]] < countT[s[l]]:
					have -= 1
				l += 1
		(l, r) = res
		if resLen != float('infinity'):
			return s[l:r + 1]
		return -1


class Solution:

	def smallestWindow(self, s, p):
		if len(s) < len(p):
			return -1
		ans = s + '1'
		i = 0
		j = -1
		m = {}
		for x in p:
			if x in m:
				m[x] += 1
			else:
				m[x] = 1
		count = 0
		while j < len(s):
			if count != len(p):
				j += 1
				if j == len(s):
					break
				if s[j] in m:
					m[s[j]] -= 1
					if m[s[j]] >= 0:
						count += 1
			else:
				if len(ans) > j - i + 1:
					ans = s[i:j + 1]
				if s[i] in m:
					m[s[i]] += 1
					if m[s[i]] > 0:
						count -= 1
				i += 1
		if ans == s + '1':
			return -1
		return ans


class Solution:

	def smallestWindow(self, s, p):
		target_freq = {}
		window_freq = {}
		for char in p:
			target_freq[char] = target_freq.get(char, 0) + 1
		required_chars = len(target_freq)
		formed_chars = 0
		left = 0
		min_window = float('inf')
		min_window_start = 0
		for (right, char) in enumerate(s):
			window_freq[char] = window_freq.get(char, 0) + 1
			if char in target_freq and window_freq[char] == target_freq[char]:
				formed_chars += 1
			while formed_chars == required_chars:
				if right - left + 1 < min_window:
					min_window = right - left + 1
					min_window_start = left
				window_freq[s[left]] -= 1
				if s[left] in target_freq and window_freq[s[left]] < target_freq[s[left]]:
					formed_chars -= 1
				left += 1
		if min_window == float('inf'):
			return '-1'
		return s[min_window_start:min_window_start + min_window]


class Solution:

	def smallestWindow(self, s, p):
		count = 0
		mp = [0] * 256
		for i in range(len(p)):
			if mp[ord(p[i])] == 0:
				count += 1
			mp[ord(p[i])] += 1
		res = float('inf')
		start = 0
		(i, j) = (0, 0)
		while j < len(s):
			mp[ord(s[j])] -= 1
			if mp[ord(s[j])] == 0:
				count -= 1
			if count == 0:
				while count == 0:
					if j - i + 1 < res:
						res = j - i + 1
						start = i
					mp[ord(s[i])] += 1
					if mp[ord(s[i])] > 0:
						count += 1
					i += 1
			j += 1
		if res == float('inf'):
			return '-1'
		else:
			return s[start:start + res]


class Solution:

	def smallestWindow(self, s, p):
		n = len(s)
		if n < len(p):
			return -1
		map = [0] * 256
		start = 0
		ans = n + 1
		count = 0
		for i in p:
			map[ord(i)] += 1
			if map[ord(i)] == 1:
				count += 1
		a = 0
		b = 0
		while a < n:
			map[ord(s[a])] -= 1
			if map[ord(s[a])] == 0:
				count -= 1
				while count == 0:
					if ans > a - b + 1:
						ans = a - b + 1
						start = b
					map[ord(s[b])] += 1
					if map[ord(s[b])] > 0:
						count += 1
					b += 1
			a += 1
		if ans > n:
			return '-1'
		return s[start:start + ans]


class Solution:

	def smallestWindow(self, s, p):
		(res, x) = (s, {})
		for i in p:
			if i in x:
				x[i] += 1
			else:
				x[i] = 1
		(c, i, j) = (0, 0, 0)
		y = {}
		while j < len(s):
			if s[j] in y:
				y[s[j]] += 1
			else:
				y[s[j]] = 1
			if s[j] in x:
				if x[s[j]] >= y[s[j]]:
					c += 1
			if c == len(p):
				while 1:
					if s[i] not in x:
						i += 1
					elif y[s[i]] > x[s[i]]:
						y[s[i]] -= 1
						i += 1
					else:
						break
				if len(s[i:j + 1]) < len(res):
					res = s[i:j + 1]
			j += 1
		if res == s:
			return -1
		return res


class Solution:

	def smallestWindow(self, s, p):
		d = {}
		for i in p:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		count = len(d)
		res = len(s)
		(i, j, st) = (0, 0, 0)
		while i < len(s):
			if s[i] in d:
				d[s[i]] -= 1
			else:
				d[s[i]] = -1
			if d[s[i]] == 0:
				count -= 1
			if count == 0:
				while count == 0:
					if res > i - j + 1:
						res = i - j + 1
						st = j
					if s[j] in d:
						d[s[j]] += 1
					if d[s[j]] > 0:
						count += 1
					j += 1
			i += 1
		if res == len(s):
			return -1
		else:
			return s[st:st + res]


class Solution:

	def smallestWindow(self, s, p):
		freqNeed = {}
		needs = 0
		for ch in p:
			if ch not in freqNeed:
				freqNeed[ch] = 0
				needs += 1
			freqNeed[ch] += 1
		i = 0
		j = 0
		minLen = float('inf')
		windowI = -1
		while i < len(s):
			while j < len(s):
				ch = s[j]
				j += 1
				if ch in freqNeed:
					freqNeed[ch] -= 1
					if freqNeed[ch] == 0:
						needs -= 1
					if needs == 0:
						if minLen > j - i:
							minLen = j - i
							windowI = i
						break
			while i < len(s):
				ch = s[i]
				i += 1
				if ch in freqNeed:
					freqNeed[ch] += 1
					if freqNeed[ch] == 1:
						needs += 1
						break
				if needs == 0:
					if minLen > j - i:
						minLen = j - i
						windowI = i
				else:
					break
		return s[windowI:windowI + minLen] if windowI != -1 else -1


from collections import Counter

class Solution:

	def smallestWindow(self, s, t):
		left = len(t)
		mp = Counter(t)
		res = s
		i = j = 0
		while j < len(s):
			if s[j] in mp:
				if mp[s[j]] > 0:
					left -= 1
				mp[s[j]] -= 1
			while not left:
				if s[i] in mp:
					mp[s[i]] += 1
					if mp[s[i]] > 0:
						left += 1
				res = min(res, s[i:j + 1], key=len)
				i += 1
			j += 1
		return res if res != s else -1


class Solution:

	def smallestWindow(self, s, p):
		if len(s) < len(p):
			return -1
		l = len(s)
		dic = {}
		ans = len(s)
		for i in p:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		c = len(dic)
		start = 0
		i = 0
		for j in range(len(s)):
			if s[j] in dic:
				dic[s[j]] -= 1
			else:
				dic[s[j]] = -1
			if dic[s[j]] == 0:
				c -= 1
			if c == 0:
				while c == 0:
					if ans > j - i + 1:
						ans = j - i + 1
						start = i
					if s[i] in dic:
						dic[s[i]] += 1
					if dic[s[i]] > 0:
						c += 1
					i += 1
		if ans == len(s):
			return -1
		return s[start:start + ans]


class Solution:

	def smallestWindow(self, s, p):
		n = len(s)
		m = len(p)
		if n < m:
			return '-1'
		char_count = {}
		for char in p:
			char_count[char] = char_count.get(char, 0) + 1
		count = 0
		left = 0
		min_len = float('inf')
		min_start = 0
		for right in range(n):
			if s[right] in char_count:
				char_count[s[right]] -= 1
				if char_count[s[right]] >= 0:
					count += 1
			while count == m:
				if right - left + 1 < min_len:
					min_len = right - left + 1
					min_start = left
				if s[left] in char_count:
					char_count[s[left]] += 1
					if char_count[s[left]] > 0:
						count -= 1
				left += 1
		if min_len == float('inf'):
			return '-1'
		return s[min_start:min_start + min_len]


class Solution:

	def smallestWindow(self, s, p):
		dict = {}
		for i in p:
			dict[i] = 1 + dict.get(i, 0)
		(have, need) = (0, len(dict))
		all = {}
		start = 0
		(result, maxi) = ('', int(1000000000.0))
		for index in range(len(s)):
			all[s[index]] = 1 + all.get(s[index], 0)
			if s[index] in dict and all[s[index]] == dict[s[index]]:
				have += 1
			while have == need:
				if index - start + 1 < maxi:
					maxi = index - start + 1
					result = s[start:index + 1]
				all[s[start]] -= 1
				if s[start] in dict and all[s[start]] < dict[s[start]]:
					have -= 1
				start += 1
		return result if result else -1


class Solution:

	def smallestWindow(self, s, p):
		countS = [0] * 26
		countP = [0] * 26
		for i in range(len(p)):
			countP[ord(p[i]) - ord('a')] += 1
		start = 0
		end = 0
		minLen = float('inf')
		minStart = 0
		count = 0
		while end < len(s):
			countS[ord(s[end]) - ord('a')] += 1
			if countS[ord(s[end]) - ord('a')] <= countP[ord(s[end]) - ord('a')]:
				count += 1
			if count == len(p):
				while countS[ord(s[start]) - ord('a')] > countP[ord(s[start]) - ord('a')]:
					countS[ord(s[start]) - ord('a')] -= 1
					start += 1
				if end - start + 1 < minLen:
					minLen = end - start + 1
					minStart = start
			end += 1
		if minLen == float('inf'):
			return '-1'
		return s[minStart:minStart + minLen]


class Solution:

	def smallestWindow(self, s, p):
		need = {}
		have = {}
		for char in p:
			need[char] = need.get(char, 0) + 1
		haveNum = 0
		needNum = len(need)
		n = len(s)
		l = r = 0
		minLen = float('inf')
		res = [-1, -1]
		while r < n:
			char = s[r]
			have[char] = have.get(char, 0) + 1
			if char in p and have[char] == need[char]:
				haveNum += 1
			while haveNum == needNum:
				if minLen > r - l + 1:
					minLen = r - l + 1
					res = [l, r + 1]
				have[s[l]] -= 1
				if s[l] in p and have[s[l]] < need[s[l]]:
					haveNum -= 1
				l += 1
			r += 1
		[l, r] = res
		return s[l:r] if [l, r] != [-1, -1] else -1


from collections import defaultdict, Counter

class Solution:

	def smallestWindow(self, s, t):
		(S, T) = (defaultdict(int), Counter(t))
		(have, need) = (0, len(T))
		l = 0
		res = [-1, -1]
		length = float('inf')
		for (r, ch) in enumerate(s):
			S[ch] += 1
			if ch in T and S[ch] == T[ch]:
				have += 1
			while have == need:
				if r - l + 1 < length:
					res = [l, r]
					length = r - l + 1
				S[s[l]] -= 1
				if s[l] in T and S[s[l]] < T[s[l]]:
					have -= 1
				l += 1
		(l, r) = res
		return s[l:r + 1] if length != float('inf') else -1


class Solution:

	def smallestWindow(self, s, p):
		d1 = {}
		d2 = {}
		cnt = 0
		for i in p:
			d1[i] = d1.get(i, 0) + 1
			cnt += 1
		i = 0
		scnt = 0
		m = len(s) + 1
		ans = ''
		for j in range(len(s)):
			d2[s[j]] = d2.get(s[j], 0) + 1
			if d2[s[j]] <= d1.get(s[j], 0):
				scnt += 1
			while scnt == cnt:
				if j - i + 1 < m:
					ans = s[i:j + 1]
					m = len(ans)
				d2[s[i]] -= 1
				if d2[s[i]] < d1.get(s[i], 0):
					scnt -= 1
				i += 1
		if ans == '':
			return -1
		return ans


class Solution:

	def smallestWindow(self, s, p):
		BestScore = float('inf')
		bestInd = ()
		arr = s
		count = len(p)
		needed = {i: 0 for i in p}
		inSdict = {i: 0 for i in p}
		for char in p:
			needed[char] += 1
		(start, end) = (0, 0)
		while count != 0:
			end += 1
			if end > len(arr):
				return -1
			if arr[end - 1] in needed:
				if needed[arr[end - 1]] > inSdict[arr[end - 1]]:
					count -= 1
				inSdict[arr[end - 1]] += 1
		BestInd = (start, end)
		while end <= len(arr) and start != end:
			if False:
				print('--------------')
				print(arr[start:end])
				if bestInd:
					print(arr[bestInd[0]:bestInd[1]])
				print(inSdict, needed)
				print(count)
			if count == 0:
				BestInd = (start, end)
				value = arr[start]
				if value in needed:
					inSdict[value] -= 1
					if needed[value] > inSdict[value]:
						count += 1
				start += 1
			else:
				valueS = arr[start]
				if valueS in needed:
					inSdict[valueS] -= 1
					if needed[valueS] > inSdict[valueS]:
						count += 1
				start += 1
				end += 1
				if end > len(arr):
					return s[BestInd[0]:BestInd[1]]
				valueE = arr[end - 1]
				if valueE in needed:
					if needed[valueE] > inSdict[valueE]:
						count -= 1
					inSdict[valueE] += 1
		return s[BestInd[0]:BestInd[1]]


class Solution:

	def smallestWindow(self, s, p):
		import collections
		p_count = collections.Counter(p)
		s_count = collections.defaultdict(int)
		window_size = float('inf')
		window_start = 0
		match_count = 0
		for window_end in range(len(s)):
			if s[window_end] in p_count:
				s_count[s[window_end]] += 1
				if s_count[s[window_end]] <= p_count[s[window_end]]:
					match_count += 1
			if match_count == len(p):
				while s[window_start] not in p_count or s_count[s[window_start]] > p_count[s[window_start]]:
					s_count[s[window_start]] -= 1
					window_start += 1
				if window_end - window_start + 1 < window_size:
					window_size = window_end - window_start + 1
					min_window = s[window_start:window_end + 1]
				match_count -= 1
				s_count[s[window_start]] -= 1
				window_start += 1
		return min_window if window_size != float('inf') else '-1'


class Solution:

	def smallestWindow(self, s, p):
		dict = {}
		ans = ''
		length = 1000000000.0
		min_start = 0
		min_end = 0
		for i in p:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		count = len(dict)
		j = 0
		for i in range(len(s)):
			if s[i] in dict:
				dict[s[i]] -= 1
				if dict[s[i]] == 0:
					count -= 1
			while count <= 0:
				if s[j] not in dict:
					pass
				elif s[j] in dict:
					dict[s[j]] += 1
					if dict[s[j]] > 0:
						count += 1
				if i - j + 1 < length:
					length = i - j + 1
					min_start = j
					min_end = i
				j += 1
		if length == 1000000000.0:
			return -1
		return s[min_start:min_end + 1]


class Solution:

	def smallestWindow(self, S, P):
		freq_p = {}
		for char in P:
			freq_p[char] = freq_p.get(char, 0) + 1
		left = right = count = 0
		min_len = float('inf')
		min_start = 0
		while right < len(S):
			if S[right] in freq_p:
				freq_p[S[right]] -= 1
				if freq_p[S[right]] >= 0:
					count += 1
			while count == len(P):
				if min_len > right - left + 1:
					min_len = right - left + 1
					min_start = left
				if S[left] in freq_p:
					freq_p[S[left]] += 1
					if freq_p[S[left]] > 0:
						count -= 1
				left += 1
			right += 1
		if min_len == float('inf'):
			return '-1'
		else:
			return S[min_start:min_start + min_len]


class Solution:

	def smallestWindow(self, s, p):
		(count_p, count_s) = (dict(), dict())
		for i in range(len(p)):
			count_p[p[i]] = count_p.get(p[i], 0) + 1
		actual = len(count_p)
		Len = 2 ** 63
		count = 0
		start = 0
		for i in range(len(s)):
			count_s[s[i]] = count_s.get(s[i], 0) + 1
			if s[i] in p and count_s[s[i]] == count_p[s[i]]:
				count += 1
			while count == actual:
				if Len > i - start + 1:
					Len = i - start + 1
					ans = s[start:i + 1]
				count_s[s[start]] -= 1
				if s[start] in p and count_s[s[start]] < count_p[s[start]]:
					count -= 1
				start += 1
		return ans if Len != 2 ** 63 else -1


class Solution:

	def smallestWindow(self, s, t):
		n = len(s)
		r = {}
		res = s
		found = False
		for c in list(t):
			if c in r:
				r[c] += 1
			else:
				r[c] = 1
		curr = ''
		for j in range(n):
			c = s[j]
			curr += c
			if c in r:
				r[c] -= 1
				while len(curr):
					all_there = True
					for k in r:
						if r[k] > 0:
							all_there = False
							break
					if all_there:
						if len(res) > len(curr):
							res = curr
							found = True
					else:
						break
					if curr[0] in r:
						r[curr[0]] += 1
					curr = curr[1:]
		if not found:
			return -1
		return res


class Solution:

	def smallestWindow(self, s, p):
		pmap = {}
		for c in p:
			pmap[c] = pmap.get(c, 0) + 1
		need = len(pmap)
		have = 0
		smap = {}
		j = 0
		res = len(s)
		final = [-1, -1]
		for i in range(len(s)):
			smap[s[i]] = smap.get(s[i], 0) + 1
			if s[i] in pmap and pmap[s[i]] == smap[s[i]]:
				have += 1
			while have == need:
				if i - j + 1 < res:
					res = i - j + 1
					final = [j, i + 1]
				smap[s[j]] -= 1
				if s[j] in pmap and smap[s[j]] < pmap[s[j]]:
					have -= 1
				j += 1
		return s[final[0]:final[1]] if final[0] != -1 else '-1'


class Solution:

	def smallestWindow(self, S, P):
		ans = S
		ct = 0
		freq = {}
		for i in P:
			if i in freq:
				freq[i] += 1
			else:
				freq[i] = 1
		i = 0
		j = 0
		new = {}
		while j < len(S):
			if S[j] in new:
				new[S[j]] += 1
			else:
				new[S[j]] = 1
			if S[j] in freq:
				if freq[S[j]] >= new[S[j]]:
					ct = ct + 1
			if ct == len(P):
				while 1:
					if S[i] not in freq:
						i = i + 1
					elif new[S[i]] > freq[S[i]]:
						new[S[i]] -= 1
						i = i + 1
					else:
						break
				if len(s[i:j + 1]) < len(ans):
					ans = s[i:j + 1]
			j += 1
		if ans == s:
			return -1
		return ans


from collections import defaultdict

class Solution:

	def smallestWindow(self, s: str, p: str) -> str:
		char_count_p = defaultdict(int)
		for c in p:
			char_count_p[c] += 1
		char_count_window = defaultdict(int)
		(start, end) = (0, 0)
		(ans_start, ans_end) = (-1, -1)
		count = 0
		while end < len(s):
			if s[end] in char_count_p:
				char_count_window[s[end]] += 1
				if char_count_window[s[end]] <= char_count_p[s[end]]:
					count += 1
			if count == len(p):
				while s[start] not in char_count_p or char_count_window[s[start]] > char_count_p[s[start]]:
					char_count_window[s[start]] -= 1
					start += 1
				if ans_start == -1 or end - start < ans_end - ans_start:
					(ans_start, ans_end) = (start, end)
				char_count_window[s[start]] -= 1
				start += 1
				count -= 1
			end += 1
		return s[ans_start:ans_end + 1] if ans_start != -1 else '-1'


class Solution:

	def smallestWindow(self, S, P):
		char_count_p = {}
		for c in P:
			char_count_p[c] = char_count_p.get(c, 0) + 1
		char_count_s = {}
		(left, right, matched, required) = (0, 0, 0, len(char_count_p))
		(min_window_len, min_window_start) = (float('inf'), None)
		while right < len(S):
			if S[right] in char_count_p:
				char_count_s[S[right]] = char_count_s.get(S[right], 0) + 1
				if char_count_s[S[right]] == char_count_p[S[right]]:
					matched += 1
				while matched == required:
					if right - left + 1 < min_window_len:
						min_window_len = right - left + 1
						min_window_start = left
					if S[left] in char_count_p:
						char_count_s[S[left]] -= 1
						if char_count_s[S[left]] < char_count_p[S[left]]:
							matched -= 1
					left += 1
			right += 1
		return S[min_window_start:min_window_start + min_window_len] if min_window_start is not None else '-1'


class Solution:

	def smallestWindow(self, s, c):
		t_map = {}
		for char in c:
			if char in t_map:
				t_map[char] += 1
			else:
				t_map[char] = 1
		left = 0
		right = 0
		min_len = float('inf')
		min_start = 0
		char_needed = len(t_map)
		window_map = {}
		while right < len(s):
			char = s[right]
			if char in t_map:
				if char in window_map:
					window_map[char] += 1
				else:
					window_map[char] = 1
				if window_map[char] == t_map[char]:
					char_needed -= 1
			while char_needed == 0:
				if right - left + 1 < min_len:
					min_len = right - left + 1
					min_start = left
				char = s[left]
				if char in t_map:
					window_map[char] -= 1
					if window_map[char] < t_map[char]:
						char_needed += 1
				left += 1
			right += 1
		if min_len == float('inf'):
			return -1
		else:
			return s[min_start:min_start + min_len]


from collections import Counter

class Solution:

	def smallestWindow(self, s, p):
		(n, m) = (len(s), len(p))
		if m > n:
			return '-1'
		count_p = Counter(p)
		start = 0
		min_len = float('inf')
		count = 0
		for i in range(n):
			if s[i] in count_p:
				count_p[s[i]] -= 1
				if count_p[s[i]] >= 0:
					count += 1
			if count == m:
				while s[start] not in count_p or count_p[s[start]] < 0:
					if s[start] in count_p:
						count_p[s[start]] += 1
					start += 1
				if i - start + 1 < min_len:
					min_len = i - start + 1
					ans_start = start
		if min_len == float('inf'):
			return '-1'
		return s[ans_start:ans_start + min_len]


class Solution:

	def smallestWindow(self, s, p):
		N = len(s)
		ans = len(s)
		dp = {}
		for i in p:
			dp[i] = dp.get(i, 0) + 1
		count = len(dp)
		(i, j, start) = (0, 0, 0)
		while j < N:
			if s[j] in dp:
				dp[s[j]] -= 1
			else:
				dp[s[j]] = -1
			if dp[s[j]] == 0:
				count -= 1
			if count == 0:
				while count == 0:
					if ans > j - i + 1:
						ans = j - i + 1
						start = i
					if s[i] in dp:
						dp[s[i]] += 1
					if dp[s[i]] > 0:
						count += 1
					i += 1
			j += 1
		return '-1' if ans == len(s) else s[start:start + ans]


class Solution:

	def smallestWindow(self, s, p):
		dict1 = {}
		for i in range(len(p)):
			dict1[p[i]] = 1 + dict1.get(p[i], 0)
		ans = ''
		mc = 0
		dmc = len(p)
		i = -1
		j = -1
		dict2 = {}
		while True:
			flag1 = 0
			flag2 = 0
			while i < len(s) - 1 and mc < dmc:
				i += 1
				dict2[s[i]] = 1 + dict2.get(s[i], 0)
				if dict1.get(s[i], 0) >= dict2.get(s[i], 0):
					mc += 1
				flag1 = 1
			while j < i and mc == dmc:
				pst = s[j + 1:i + 1]
				if len(ans) == 0 or len(pst) < len(ans):
					ans = pst
				j += 1
				if dict2.get(s[j], 0) == 1:
					dict2.pop(s[j])
				else:
					dict2[s[j]] -= 1
				if dict2.get(s[j], 0) < dict1.get(s[j], 0):
					mc -= 1
				flag2 = 1
			if flag1 == 0 and flag2 == 0:
				break
		if len(ans) == 0:
			return -1
		return ans


class Solution:

	def smallestWindow(self, s, p):
		dic = dict()
		for i in p:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		i = j = 0
		count = len(dic)
		mi = ''
		while j in range(len(s)):
			if s[j] in dic:
				dic[s[j]] -= 1
				if dic[s[j]] == 0:
					count -= 1
				while count == 0:
					if len(mi) == 0:
						mi = s[i:j + 1]
					elif len(mi) > j - i + 1:
						mi = s[i:j + 1]
					if s[i] in dic:
						dic[s[i]] += 1
						if dic[s[i]] > 0:
							count += 1
					i += 1
			j += 1
		if mi == '':
			return -1
		return mi


class Solution:

	def smallestWindow(self, s, p):
		pattern = [0] * 128
		string = [0] * 128
		count = 0
		n = len(s)
		m = len(p)
		for i in range(m):
			pattern[ord('a') - ord(p[i])] += 1
		(i, start) = (0, -1)
		(j, end) = (0, n)
		while j < n:
			string[ord('a') - ord(s[j])] += 1
			if string[ord('a') - ord(s[j])] <= pattern[ord('a') - ord(s[j])]:
				count += 1
			if count == m:
				while pattern[ord('a') - ord(s[i])] < string[ord('a') - ord(s[i])] or pattern[ord('a') - ord(s[i])] == 0:
					if pattern[ord('a') - ord(s[i])] < string[ord('a') - ord(s[i])]:
						string[ord('a') - ord(s[i])] -= 1
					i += 1
				if j - i < end - start:
					start = i
					end = j
			j += 1
		if start == -1:
			return '-1'
		return s[start:end + 1]


class Solution:

	def smallestWindow(self, s, p):
		frequencyP = {}
		for ch in p:
			frequencyP[ch] = frequencyP.get(ch, 0) + 1
		(start, end) = (0, 0)
		count = len(p)
		minLen = float('inf')
		minStart = 0
		while end < len(s):
			if s[end] in frequencyP:
				frequencyP[s[end]] -= 1
				if frequencyP[s[end]] >= 0:
					count -= 1
			while count == 0:
				if end - start + 1 < minLen:
					minLen = end - start + 1
					minStart = start
				if s[start] in frequencyP:
					frequencyP[s[start]] += 1
					if frequencyP[s[start]] > 0:
						count += 1
				start += 1
			end += 1
		if minLen == float('inf'):
			return -1
		return s[minStart:minStart + minLen]