Given a string 's'. The task is to find the smallest window length that contains all the characters of the given string at least one time.
For eg. A = aabcbcdbca, then the result would be 4 as of the smallest window will be dbca.
 
Example 1:
Input : "AABBBCBBAC"
Output : 3
Explanation : Sub-string -> "BAC"
Example 2:
Input : "aaab"
Output : 2
Explanation : Sub-string -> "ab"
 
Example 3:
Input : "GEEKSGEEKSFOR"
Output : 8
Explanation : Sub-string -> "GEEKSFOR"
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findSubString() which takes the string  S as input and returns the length of the smallest such window of the string.
Expected Time Complexity: O(256.N)
Expected Auxiliary Space: O(256)
 
Constraints:
1 ≤ |S| ≤ 10^{5}
String may contain both type of English Alphabets.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def findSubString(self, str):

        # Your code goes here

    

    

    

Solutions:
class Solution:

	def findSubString(self, str):
		dict = {}
		ans = float('inf')
		j = 0
		for i in str:
			if i not in dict:
				dict[i] = 0
		length = len(dict)
		for i in range(len(str)):
			dict[str[i]] += 1
			if dict[str[i]] == 1:
				length -= 1
			while length == 0:
				ans = min(ans, i - j + 1)
				dict[str[j]] -= 1
				if dict[str[j]] == 0:
					length += 1
				j += 1
		return ans


from collections import defaultdict

class Solution:

	def findSubString(self, s):
		n = len(s)
		dist_count = len(set([x for x in s]))
		m = defaultdict(int)
		start = 0
		min_len = float('inf')
		count = 0
		for j in range(n):
			m[s[j]] += 1
			if m[s[j]] == 1:
				count += 1
			if count == dist_count:
				while m[s[start]] > 1:
					if m[s[start]] > 1:
						m[s[start]] -= 1
					start += 1
				len_window = j - start + 1
				if min_len > len_window:
					min_len = len_window
		return min_len


class Solution:

	def findSubString(self, str):
		from collections import defaultdict
		n = len(str)
		if n <= 1:
			return 1
		dist_count = len(set([x for x in str]))
		curr_count = defaultdict(lambda : 0)
		count = 0
		start = 0
		min_len = n
		for j in range(n):
			curr_count[str[j]] += 1
			if curr_count[str[j]] == 1:
				count += 1
			if count == dist_count:
				while curr_count[str[start]] > 1:
					if curr_count[str[start]] > 1:
						curr_count[str[start]] -= 1
					start += 1
				len_window = j - start + 1
				min_len = min(min_len, len_window)
				start_index = start
		return min_len


class Solution:

	def findSubString(self, s):
		D = {}
		for i in s:
			if i in D:
				pass
			else:
				D[i] = 1
		n = len(s)
		(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:
				mini = min(mini, j - i + 1)
				if s[i] in D:
					D[s[i]] += 1
					if D[s[i]] > 0:
						count += 1
				i += 1
			j += 1
		return mini


class Solution:

	def findSubString(self, str):
		mp = {}
		cnt = 0
		for i in range(len(str)):
			if str[i] not in mp:
				mp[str[i]] = 0
				cnt += 1
		cnt1 = 0
		j = 0
		mn = len(str)
		for i in range(len(str)):
			if mp[str[i]] == 0:
				mp[str[i]] += 1
				cnt1 += 1
			else:
				mp[str[i]] += 1
			while cnt == cnt1:
				mn = min(mn, i - j + 1)
				if mp[str[j]] == 1:
					mp[str[j]] -= 1
					cnt1 -= 1
					j = j + 1
				else:
					mp[str[j]] -= 1
					j = j + 1
		return mn


class Solution:

	def findSubString(self, str):
		dict = {}
		a = 1000000000.0
		j = 0
		for i in str:
			if i not in dict:
				dict[i] = 0
		l = len(dict)
		for i in range(len(str)):
			dict[str[i]] += 1
			if dict[str[i]] == 1:
				l -= 1
			while l == 0:
				a = min(a, i - j + 1)
				dict[str[j]] -= 1
				if dict[str[j]] == 0:
					l += 1
				j += 1
		return a


class Solution:

	def findSubString(self, s):
		distinct = len(set(s))
		d = dict()
		si = -1
		Len = 100000.0
		start = 0
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = 1
			else:
				d[s[i]] += 1
			if len(d) == distinct:
				while d[s[start]] > 1:
					d[s[start]] -= 1
					start += 1
				clen = i - start + 1
				if Len > clen:
					Len = clen
					si = start
		return len(s[si:si + Len])


from collections import defaultdict

class Solution:

	def findSubString(self, str):
		leng = len(str)
		(start, end) = (0, leng - 1)
		ct = 0
		t_dist = len(set([e for e in str]))
		chr_map = defaultdict(lambda : 0)
		min_wind = leng
		for i in range(leng):
			x = str[i]
			chr_map[x] += 1
			if chr_map[x] == 1:
				ct += 1
			if ct == t_dist:
				while chr_map[str[start]] > 1:
					chr_map[str[start]] -= 1
					start += 1
				min_wind = min(i - start + 1, min_wind)
		return min_wind


class Solution:

	def findSubString(self, str):
		n = len(str)
		(dic, vic) = ({}, {})
		for a in str:
			if a not in dic:
				dic[a] = 0
			dic[a] += 1
		(i, j, ans) = (0, 0, 10000000000)
		while j < n:
			if str[j] not in vic:
				vic[str[j]] = 0
			vic[str[j]] += 1
			if len(vic) == len(dic):
				while len(vic) == len(dic):
					vic[str[i]] -= 1
					if vic[str[i]] == 0:
						del vic[str[i]]
					i += 1
				ans = min(ans, 2 + j - i)
			j += 1
		return ans


class Solution:

	def findSubString(self, str):
		dict = {}
		ans = 1000000000.0
		for i in str:
			if i not in dict:
				dict[i] = 0
		length = len(dict)
		count = 0
		j = 0
		for i in range(len(str)):
			dict[str[i]] += 1
			if dict[str[i]] == 1:
				count += 1
			while count == length:
				ans = min(ans, i - j + 1)
				dict[str[j]] -= 1
				if dict[str[j]] == 0:
					count -= 1
				j += 1
		return ans


from collections import Counter

class Solution:

	def findSubString(self, str1):
		length = len(str1)
		dict1 = Counter(str1)
		k = len(dict1)
		dict2 = dict()
		count = 0
		start = 0
		minimum = 99999
		for i in range(length):
			if count < k:
				j = start
				while j < length:
					if str1[j] not in dict2:
						dict2[str1[j]] = 1
						count += 1
					else:
						dict2[str1[j]] += 1
					if count == k:
						break
					j += 1
			if count == k:
				minimum = min(minimum, j - i + 1)
				start = j + 1
			dict2[str1[i]] -= 1
			if dict2[str1[i]] == 0:
				dict2.pop(str1[i])
				count -= 1
		return minimum


from collections import Counter, defaultdict

class Solution:

	def findSubString(self, str_):
		set_of_string = set()
		len_set_of_string = len(set(str_))
		answer = float('inf')
		left = 0
		right = 0
		freq = defaultdict(int)
		while right < len(str_):
			freq[str_[right]] += 1
			while left <= right and len(freq) == len_set_of_string:
				answer = min(answer, right - left + 1)
				freq[str_[left]] -= 1
				if freq[str_[left]] == 0:
					del freq[str_[left]]
				left += 1
			right += 1
		return answer


class Solution:

	def findSubString(self, a):
		dict = {}
		n = len(set(a))
		left = 0
		right = 0
		ans = len(a)
		while right < len(a):
			if a[right] not in dict:
				dict[a[right]] = 1
			else:
				dict[a[right]] += 1
			if len(dict) == n:
				while dict[a[left]] > 1:
					dict[a[left]] -= 1
					left += 1
				ans = min(ans, right - left + 1)
			right += 1
		return ans


import math

class Solution:

	def findSubString(self, s):
		dicti = {}
		mini = math.inf
		k = len(set(s))
		n = len(s)
		(i, j) = (0, 0)
		while j < n:
			if s[j] not in dicti:
				dicti[s[j]] = 1
			else:
				dicti[s[j]] += 1
			if len(dicti) < k:
				j += 1
			elif len(dicti) == k:
				while len(dicti) == k:
					mini = min(mini, j - i + 1)
					if s[i] in dicti:
						dicti[s[i]] -= 1
						if dicti[s[i]] == 0:
							del dicti[s[i]]
					i += 1
				j += 1
		return mini


from collections import defaultdict

class Solution:

	def findSubString(self, arr):
		dic = defaultdict(lambda : 0)
		i = 0
		j = 0
		n = len(set(arr))
		ans = len(arr)
		while j < len(arr):
			dic[arr[j]] += 1
			if len(dic) < n:
				j += 1
			if len(dic) == n:
				while dic[arr[i]] > 1:
					dic[arr[i]] -= 1
					i += 1
				ans = min(ans, j - i + 1)
				j += 1
		return ans


class Solution:

	def findSubString(self, str):
		d = {}
		for i in str:
			d[i] = 0
		i = 0
		j = 0
		ans = len(str)
		count = len(d)
		temp = 0
		while j < len(str):
			while temp < count and j < len(str):
				if d[str[j]] == 0:
					temp += 1
				d[str[j]] += 1
				j += 1
			while temp >= count:
				d[str[i]] -= 1
				if d[str[i]] == 0:
					temp -= 1
				i += 1
			ans = min(ans, j - i + 1)
		return ans


from collections import deque

class Solution:

	def findSubString(self, stre):
		s = set(stre)
		set_len = len(s)
		j = 0
		minlen = 1000000000.0
		mp = {}
		n = len(stre)
		for i in range(n):
			if stre[i] not in mp:
				mp[stre[i]] = 1
			else:
				mp[stre[i]] += 1
			while j <= i and len(mp) == set_len:
				if minlen > i - j + 1:
					minlen = i - j + 1
				mp[stre[j]] -= 1
				if mp[stre[j]] == 0:
					del mp[stre[j]]
				j += 1
		return minlen


class Solution:

	def findSubString(self, str):
		m = {}
		n = len(set(str))
		length = float('inf')
		j = 0
		for i in range(len(str)):
			m[str[i]] = m.get(str[i], 0) + 1
			if len(m) == n:
				while m[str[j]] > 1:
					m[str[j]] -= 1
					j += 1
				length = min(length, i - j + 1)
		return length


class Solution:

	def findSubString(self, str):
		dict = {}
		ans = 1000000000.0
		for i in str:
			if i not in dict:
				dict[i] = 1
		dict2 = {}
		j = 0
		for i in range(len(str)):
			if str[i] not in dict2:
				dict2[str[i]] = 1
			else:
				dict2[str[i]] += 1
			while len(dict) == len(dict2):
				ans = min(ans, i - j + 1)
				if dict2[str[j]] > 1:
					dict2[str[j]] -= 1
				elif dict2[str[j]] == 1:
					dict2.pop(str[j])
				j += 1
		return ans


from collections import defaultdict

class Solution:

	def findSubString(self, s):
		a = set(s)
		i = 0
		t = {}
		min_len = float('inf')
		for j in range(len(s)):
			if s[j] not in t:
				t[s[j]] = 0
			t[s[j]] += 1
			while len(t) == len(a):
				min_len = min(min_len, j - i + 1)
				t[s[i]] -= 1
				if t[s[i]] == 0:
					del t[s[i]]
				i += 1
		return min_len


class Solution:

	def findSubString(self, str):
		from collections import defaultdict
		curr_count = defaultdict(lambda : 0)
		dist_count = len(set([x for x in str]))
		if len(str) <= 1:
			return 1
		counter = 0
		start = 0
		min_len = len(str)
		for i in range(len(str)):
			curr_count[str[i]] += 1
			if curr_count[str[i]] == 1:
				counter += 1
			if counter == dist_count:
				while curr_count[str[start]] > 1:
					if curr_count[str[start]] > 1:
						curr_count[str[start]] -= 1
					start += 1
				window_len = i - start + 1
				if window_len < min_len:
					min_len = window_len
					start_index = start
		a = min_len
		return a


class Solution:

	def findSubString(self, str):
		d = {}
		for i in str:
			if i not in d:
				d[i] = 0
		(i, j) = (0, float('inf'))
		(count, out) = (0, float('inf'))
		for j in range(len(str)):
			if d[str[j]] == 0:
				count += 1
			d[str[j]] += 1
			if count == len(d):
				while i < j:
					d[str[i]] -= 1
					if d[str[i]] == 0:
						out = min(out, j - i + 1)
						count -= 1
						i += 1
						break
					i += 1
		return out if out != float('inf') else 1


class Solution:

	def findSubString(self, str):
		k = len(set(str))
		memo = {}
		ans = len(str)
		(i, j) = (0, 0)
		while j < len(str):
			memo[str[j]] = memo.get(str[j], 0) + 1
			if len(memo) < k:
				j += 1
			elif len(memo) == k:
				while len(memo) == k:
					memo[str[i]] -= 1
					if memo[str[i]] == 0:
						del memo[str[i]]
					i += 1
				ans = min(ans, j - i + 2)
				j += 1
			elif len(memo) > k:
				while len(memo) > k:
					memo[str[i]] -= 1
					if memo[str[i]] == 0:
						del memo[str[i]]
					i += 1
				j += 1
		return ans


class Solution:

	def findSubString(self, str):
		res = 100000
		d = {}
		for i in range(len(str)):
			if str[i] not in d:
				d[str[i]] = 0
		s1 = set()
		count = len(d)
		l = 0
		for i in range(len(str)):
			s1.add(str[i])
			d[str[i]] = d[str[i]] + 1
			while count == len(s1) and d[str[l]] != 0:
				d[str[l]] = d[str[l]] - 1
				if d[str[l]] == 0:
					s1.remove(str[l])
					res = min(res, i - l + 1)
				l = l + 1
		return res


class Solution:

	def findSubString(self, str):
		ans = len(str)
		N = len(str)
		n = len(set(str))
		(i, j) = (0, 0)
		d = {}
		while i < N:
			if str[i] not in d:
				d[str[i]] = 1
			else:
				d[str[i]] += 1
			if len(d) == n:
				while d[str[j]] > 1:
					d[str[j]] -= 1
					j += 1
				ans = min(ans, i - j + 1)
			i += 1
		return ans


class Solution:

	def findSubString(self, s):
		freq = {}
		for c in s:
			freq[c] = 0
		unique_chars = len(freq)
		left = 0
		right = 0
		count = 0
		min_length = float('inf')
		while right < len(s):
			if s[right] in freq:
				freq[s[right]] += 1
				if freq[s[right]] == 1:
					count += 1
			right += 1
			while count == unique_chars:
				if right - left < min_length:
					min_length = right - left
				if s[left] in freq:
					freq[s[left]] -= 1
					if freq[s[left]] == 0:
						count -= 1
				left += 1
		return min_length


class Solution:

	def findSubString(self, str):
		d = {}
		for i in str:
			if i not in d:
				d[i] = 0
		x = len(d)
		ans = 999999
		i = 0
		j = 0
		c = 0
		while i < len(str):
			if d[str[i]] == 0:
				c += 1
			d[str[i]] += 1
			if c == x:
				f = True
				while c == x:
					ans = min(ans, i - j + 1)
					d[str[j]] -= 1
					if d[str[j]] == 0:
						c -= 1
					j += 1
			i += 1
		return ans


class Solution:

	def findSubString(self, str):
		reslen = len(str)
		s = set()
		d = dict()
		for i in range(len(str)):
			s.add(str[i])
		i = 0
		count = 0
		for j in range(len(str)):
			d[str[j]] = d.get(str[j], 0) + 1
			if d[str[j]] == 1:
				count += 1
			if count == len(s):
				while d[str[i]] > 1:
					if d[str[i]] > 1:
						d[str[i]] -= 1
					i += 1
				if reslen > j - i + 1:
					reslen = j - i + 1
		return reslen


from collections import defaultdict

class Solution:

	def findSubString(self, strr):
		n = len(strr)
		dist_count = len(set([x for x in strr]))
		if n == dist_count:
			return n
		curr_count = dict()
		count = 0
		start = 0
		min_len = n
		for i in range(n):
			curr_count[strr[i]] = curr_count.get(strr[i], 0) + 1
			if curr_count[strr[i]] == 1:
				count += 1
			if count == dist_count:
				while curr_count[strr[start]] > 1:
					if curr_count[strr[start]] > 1:
						curr_count[strr[start]] -= 1
					start += 1
				if min_len > i - start + 1:
					min_len = i - start + 1
		return min_len


class Solution:

	def findSubString(self, s):
		n = len(s)
		res = n
		i = 0
		uniq = set(list(s))
		found = {}
		for j in range(n):
			if s[j] in found:
				found[s[j]] += 1
			else:
				found[s[j]] = 1
			while i < j:
				if found[s[i]] > 1:
					found[s[i]] -= 1
					i += 1
				else:
					break
			if len(found) == len(uniq):
				res = min(res, j - i + 1)
		return res


from collections import defaultdict

class Solution:

	def findSubString(self, s):
		n = len(s)
		if n <= 1:
			return len(s)
		dis_char = len(set(list(s)))
		curr = defaultdict(lambda : 0)
		cnt = 0
		minlen = n
		start = 0
		for j in range(n):
			curr[s[j]] += 1
			if curr[s[j]] == 1:
				cnt += 1
			if cnt == dis_char:
				while curr[s[start]] > 1:
					curr[s[start]] -= 1
					start += 1
				length = j - start + 1
				if length < minlen:
					minlen = length
					startind = start
		return minlen


class Solution:

	def findSubString(self, S):
		distinct_chars = set(S)
		n = len(S)
		left = 0
		min_length = n
		count = [0] * 256
		distinct = 0
		for right in range(n):
			count[ord(S[right])] += 1
			if count[ord(S[right])] == 1:
				distinct += 1
			if distinct == len(distinct_chars):
				while count[ord(S[left])] > 1:
					count[ord(S[left])] -= 1
					left += 1
				min_length = min(min_length, right - left + 1)
				count[ord(S[left])] -= 1
				left += 1
				distinct -= 1
		return min_length


class Solution:

	def findSubString(self, str):
		maxi = len(str)
		sets = set(str)
		i = 0
		j = 0
		m = {}
		while i < len(str):
			m[str[i]] = 1 + m.get(str[i], 0)
			if len(m) >= len(sets):
				while m[str[j]] > 1:
					m[str[j]] -= 1
					j += 1
				maxi = min(maxi, i - j + 1)
			i += 1
		return maxi


class Solution:

	def findSubString(self, input_string):
		start = 0
		end = 1
		alphabet_dict = {}
		distinct_list = list(set(input_string))
		for i in range(0, len(distinct_list)):
			alphabet_dict[distinct_list[i]] = 0
		n = len(distinct_list)
		count = 1
		alphabet_dict[input_string[0]] = 1
		answer = len(input_string)
		while start <= end < len(input_string):
			if count < n:
				element = input_string[end]
				if alphabet_dict[element] == 0:
					alphabet_dict[element] = 1
					count = count + 1
				else:
					alphabet_dict[element] = alphabet_dict[element] + 1
				end = end + 1
			elif count == n:
				answer = min(answer, end - start)
				element = input_string[start]
				if element in alphabet_dict and alphabet_dict[element] == 1:
					count = count - 1
				alphabet_dict[element] = alphabet_dict[element] - 1
				start = start + 1
		while count == n:
			answer = min(answer, end - start)
			element = input_string[start]
			if element in alphabet_dict and alphabet_dict[element] == 1:
				count = count - 1
			alphabet_dict[element] = alphabet_dict[element] - 1
			start = start + 1
		return answer


from collections import Counter

class Solution:

	def findSubString(self, str):
		dic1 = Counter(str)
		dic2 = dict()
		(i, j) = (0, 0)
		res = 10000000000
		while j < len(str):
			if str[j] in dic2:
				dic2[str[j]] += 1
			else:
				dic2[str[j]] = 1
			if len(dic1) == len(dic2):
				while len(dic1) == len(dic2):
					res = min(res, j - i + 1)
					dic2[str[i]] -= 1
					if dic2[str[i]] == 0:
						del dic2[str[i]]
					i += 1
			j += 1
		return res


import math

class Solution:

	def findSubString(self, s):
		freq = {}
		for c in s:
			freq[c] = 0
		(b, d, ans) = (0, 0, math.inf)
		for (i, c) in enumerate(s):
			while d == len(freq.keys()):
				freq[s[b]] -= 1
				if freq[s[b]] == 0:
					ans = min(ans, i - b)
					d -= 1
				b += 1
			freq[c] += 1
			if freq[c] == 1:
				d += 1
		while d == len(freq.keys()):
			freq[s[b]] -= 1
			if freq[s[b]] == 0:
				ans = min(ans, i - b + 1)
				d -= 1
			b += 1
		return ans


class Solution:

	def findSubString(self, str):
		n = len(str)
		ans = 0
		length = n
		s = list(set(str))
		d = dict()
		count = 0
		start = 0
		for i in range(n):
			if str[i] not in d.keys():
				d[str[i]] = 1
				count += 1
			else:
				d[str[i]] += 1
			if count == len(s):
				while d[str[start]] > 1:
					d[str[start]] -= 1
					start += 1
				ans = i - start + 1
				if length > ans:
					length = ans
		return length


from collections import defaultdict

class Solution:

	def findSubString(self, s):
		control = set(s)
		m = len(control)
		n = len(s)
		test = defaultdict(lambda : 0)
		mini = float('inf')
		i = 0
		for j in range(n):
			while len(test) < m and i < n:
				test[s[i]] += 1
				i += 1
			if len(test) < m:
				break
			mini = min(mini, i - j)
			test[s[j]] -= 1
			if test[s[j]] == 0:
				del test[s[j]]
		return mini


class Solution:

	def findSubString(self, str):
		i = 0
		j = 0
		s = len(set(str))
		n = len(str)
		ans = n
		dic = {}
		while i < n:
			if str[i] not in dic:
				dic[str[i]] = 1
			else:
				dic[str[i]] += 1
			if len(dic) == s:
				while dic[str[j]] > 1:
					dic[str[j]] -= 1
					j += 1
				ans = min(ans, i - j + 1)
			i += 1
		return ans


class Solution:

	def findSubString(self, s):
		n = len(s)
		distinct_chars = len(set(s))
		freq = [0] * 256
		left = 0
		right = 0
		count = 0
		min_len = n
		while right < n:
			ch = ord(s[right])
			if freq[ch] == 0:
				count += 1
			freq[ch] += 1
			right += 1
			while count == distinct_chars:
				min_len = min(min_len, right - left)
				ch = ord(s[left])
				freq[ch] -= 1
				if freq[ch] == 0:
					count -= 1
				left += 1
		return min_len


class Solution:

	def findSubString(self, str):
		nd = len(set(str))
		i = 0
		j = 0
		res = len(str)
		dic = {}
		while i < len(str):
			if str[i] in dic:
				dic[str[i]] = dic[str[i]] + 1
			else:
				dic[str[i]] = 1
			if len(dic) == nd:
				while dic[str[j]] > 1:
					dic[str[j]] = dic[str[j]] - 1
					j = j + 1
				res = min(res, i - j + 1)
			i = i + 1
		return res


from collections import Counter

class Solution:

	def findSubString(self, str1):
		dict1 = dict()
		count = 0
		distinct = len(Counter(str1))
		n = len(str1)
		j = 0
		minimum = n
		for i in range(n):
			if count < distinct:
				while j < n:
					if str1[j] not in dict1:
						dict1[str1[j]] = 1
						count += 1
					else:
						dict1[str1[j]] += 1
					if count == distinct:
						j += 1
						break
					j += 1
			if count == distinct:
				minimum = min(minimum, j - i)
			dict1[str1[i]] -= 1
			if dict1[str1[i]] == 0:
				dict1.pop(str1[i])
				count -= 1
		return minimum


class Solution:

	def findSubString(self, a):
		s = ''
		a1 = {}
		for i in a:
			a1[i] = 1
		c1 = len(a1)
		i = 0
		j = 0
		a2 = {}
		c = 0
		res = len(a)
		while j < len(a):
			if a[j] not in a2:
				a2[a[j]] = 0
				c += 1
			a2[a[j]] += 1
			while i <= j and c == c1:
				res = min(res, j - i + 1)
				a2[a[i]] -= 1
				if a2[a[i]] == 0:
					del a2[a[i]]
					c -= 1
				i += 1
			j += 1
		return res


class Solution:

	def findSubString(self, str):
		ans_len = len(set(str))
		d = {}
		ws = 0
		ans = 10 ** 6
		for we in range(0, len(str)):
			d[str[we]] = d.get(str[we], 0) + 1
			if len(d) == ans_len:
				while d[str[ws]] > 1:
					d[str[ws]] -= 1
					ws += 1
				ans = min(ans, we - ws + 1)
		return ans


class Solution:

	def findSubString(self, str):
		unique = set(str)
		res = len(str)
		j = 0
		map = dict()
		for i in range(0, len(str)):
			if str[i] in map.keys():
				map[str[i]] += 1
			else:
				map[str[i]] = 1
			if len(unique) == len(map):
				while map[str[j]] > 1:
					map[str[j]] -= 1
					j += 1
				res = min(res, i - j + 1)
		return res


class Solution:

	def findSubString(self, str):
		l = len(str)
		s = set()
		for i in range(len(str)):
			s.add(str[i])
		n = len(s)
		head = 0
		tail = 0
		hmap = {}
		ans = l
		while head < l:
			if str[head] in hmap:
				hmap[str[head]] += 1
			else:
				hmap[str[head]] = 1
			if len(hmap) == n:
				while hmap[str[tail]] > 1:
					hmap[str[tail]] -= 1
					tail += 1
				ans = min(ans, head - tail + 1)
			head += 1
		return ans


from collections import defaultdict, Counter
from sys import maxsize

class Solution:

	def findSubString(self, str):
		cnt = Counter(str)
		cur = defaultdict(int)
		k = 0
		ans = maxsize
		i = 0
		for (j, ch) in enumerate(str):
			cur[ch] += 1
			if cur[ch] == 1:
				k += 1
			if k == len(cnt):
				while i < j:
					if cur[str[i]] == 1:
						break
					cur[str[i]] -= 1
					i += 1
				ans = min(ans, j - i + 1)
		return ans


class Solution:

	def findSubString(self, str):
		res = float('inf')
		(i, j) = (0, 0)
		maxLen = len(set(list(str)))
		hashmap = {}
		while j < len(str):
			if str[j] not in hashmap:
				hashmap[str[j]] = 1
			else:
				hashmap[str[j]] += 1
			j += 1
			if len(hashmap) == maxLen:
				while i < j and hashmap[str[i]] > 1:
					hashmap[str[i]] -= 1
					i += 1
				res = min(res, j - i)
		return res


class Solution:

	def findSubString(self, str):
		d = {}
		for ch in str:
			if ch not in d:
				d[ch] = 1
		n = len(d)
		d.clear()
		i = 0
		j = 0
		count = 0
		mini = len(str)
		while j < len(str):
			if str[j] not in d:
				d[str[j]] = 1
				count = count + 1
			else:
				d[str[j]] = d[str[j]] + 1
			if count == n:
				while d[str[i]] != 1:
					d[str[i]] = d[str[i]] - 1
					i = i + 1
				mini = min(mini, j - i + 1)
			j = j + 1
		return mini


class Solution:

	def findSubString(self, s):
		n = len(s)
		d = {}
		count = 0
		for i in range(n):
			d[s[i]] = 0
		i = 0
		j = 0
		ans = n
		while i < n:
			if d[s[i]] == 0:
				count += 1
			d[s[i]] += 1
			if count == len(d):
				while j < n and d[s[j]] > 1:
					d[s[j]] -= 1
					j += 1
				if ans > i - j + 1:
					ans = i - j + 1
			i += 1
		return ans


class Solution:

	def findSubString(self, str):
		p = len(set(str))
		j = 0
		i = 0
		d = {}
		mn = 100000
		while j < len(str):
			if str[j] in d:
				d[str[j]] += 1
			else:
				d[str[j]] = 1
			if len(d) == p:
				while len(d) == p:
					mn = min(mn, j - i + 1)
					d[str[i]] -= 1
					if d[str[i]] == 0:
						del d[str[i]]
					i += 1
			j += 1
		return mn


class Solution:

	def findSubString(self, str):
		d = {}
		i = 0
		j = 0
		sw = 100000000
		n = len(set(str))
		while j < len(str):
			if str[j] not in d:
				d[str[j]] = 1
			else:
				d[str[j]] += 1
			if len(d) == n:
				while len(d) == n:
					sw = min(sw, j - i + 1)
					d[str[i]] -= 1
					if d[str[i]] == 0:
						del d[str[i]]
					i += 1
			j += 1
		return sw


class Solution:

	def findSubString(self, str):
		dict = {}
		for i in str:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		count = len(list(dict.keys()))
		i = j = 0
		ans = len(str)
		c = 0
		dict = {}
		for i in range(len(str)):
			if str[i] in dict:
				dict[str[i]] += 1
			else:
				dict[str[i]] = 1
				c += 1
			if c == count:
				ans = min(ans, i - j + 1)
				while c == count and j <= i:
					dict[str[j]] -= 1
					if dict[str[j]] == 0:
						del dict[str[j]]
						c -= 1
					ans = min(ans, i - j + 1)
					j += 1
		return ans


class Solution:

	def findSubString(self, str):
		s = set(str)
		n = len(s)
		ss = set()
		ind = 0
		d = {}
		mini = 10 ** 9
		for i in range(len(str)):
			if str[i] not in ss:
				ss.add(str[i])
			d[str[i]] = d.get(str[i], 0) + 1
			if len(ss) == n:
				ind = i + 1
				mini = min(mini, i + 1)
				break
		index = 0
		while d[str[index]] > 1:
			d[str[index]] -= 1
			index += 1
			mini = min(mini, i - index + 1)
		for i in range(ind, len(str)):
			d[str[i]] = d.get(str[i], 0) + 1
			while d[str[index]] > 1:
				d[str[index]] -= 1
				index += 1
				mini = min(mini, i - index + 1)
		while d[str[index]] > 1:
			d[str[index]] -= 1
			index += 1
			mini = min(mini, i - index + 1)
		return mini