Given a string you need to print the size of the longest possible substring that has exactly K unique characters. If there is no possible substring then print -1.
Example 1:
Input:
S = "aabacbebebe", K = 3
Output: 7
Explanation: "cbebebe" is the longest 
substring with K distinct characters.
Example 2:
Input: 
S = "aaaa", K = 2
Output: -1
Explanation: There's no substring with K
distinct characters.
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestKSubstr() which takes the string S and an integer K as input and returns the length of the longest substring with exactly K distinct characters. If there is no substring with exactly K distinct characters then return -1.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
Constraints:
1 ≤ |S| ≤ 10^{5}
1 ≤ K ≤ 10^{5}
All characters are lowercase latin characters.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:



    def longestKSubstr(self, s, k):

        # code here

Solutions:
class Solution:

	def longestKSubstr(self, s, k):
		l = 0
		count = {}
		maxLen = float('-inf')
		for r in range(len(s)):
			if s[r] not in count:
				count[s[r]] = 0
			count[s[r]] += 1
			while len(count) > k:
				count[s[l]] -= 1
				if count[s[l]] == 0:
					del count[s[l]]
				l += 1
			if len(count) == k:
				maxLen = max(maxLen, r - l + 1)
		return -1 if maxLen == float('-inf') else maxLen


class Solution:

	def longestKSubstr(self, s, k):
		ump = {}
		ump1 = {}
		start = 0
		maxi = -1
		if len(s) < k:
			return maxi
		for i in range(len(s)):
			ump1[s[i]] = ump1.get(s[i], 0) + 1
		if len(ump1) < k:
			return maxi
		for end in range(len(s)):
			ump[s[end]] = ump.get(s[end], 0) + 1
			while len(ump) > k:
				ump[s[start]] = ump.get(s[start], 0) - 1
				if ump[s[start]] == 0:
					del ump[s[start]]
				start += 1
			maxi = max(maxi, end - start + 1)
		return maxi


class Solution:

	def longestKSubstr(self, s, k):
		n = len(s)
		if len(set(s)) < k:
			return -1
		count = [0] * 26
		distinct = 0
		ans = 0
		i = j = 0
		while j < n:
			if count[ord(s[j]) - ord('a')] == 0:
				distinct += 1
			count[ord(s[j]) - ord('a')] += 1
			while distinct > k:
				count[ord(s[i]) - ord('a')] -= 1
				if count[ord(s[i]) - ord('a')] == 0:
					distinct -= 1
				i += 1
			if distinct == k:
				ans = max(ans, j - i + 1)
			j += 1
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		n = len(s)
		freq = [0] * 26
		start = 0
		distinct_count = 0
		max_len = -1
		for end in range(n):
			char_index = ord(s[end]) - ord('a')
			freq[char_index] += 1
			if freq[char_index] == 1:
				distinct_count += 1
			while distinct_count > k:
				freq[ord(s[start]) - ord('a')] -= 1
				if freq[ord(s[start]) - ord('a')] == 0:
					distinct_count -= 1
				start += 1
			if distinct_count == k:
				max_len = max(max_len, end - start + 1)
		return max_len


from collections import defaultdict, deque

class Solution:

	def longestKSubstr(self, s, k):
		mp = defaultdict(int)
		dq = deque()
		cnt = 0
		result = -1
		for i in s:
			if cnt == k and mp[i] == 0:
				result = max(result, len(dq))
				while cnt == k:
					mp[dq[0]] -= 1
					if mp[dq[0]] == 0:
						cnt -= 1
					dq.popleft()
				mp[i] += 1
				cnt += 1
				dq.append(i)
			else:
				if mp[i] == 0:
					cnt += 1
				mp[i] += 1
				dq.append(i)
		if cnt == k:
			result = max(result, len(dq))
		return result


class Solution:

	def longestKSubstr(self, s, k):
		(start, longest) = (0, -1)
		d = {}
		for (end, ch) in enumerate(s):
			d[ch] = d.get(ch, 0) + 1
			while len(d) > k:
				stChar = s[start]
				d[stChar] -= 1
				if d[stChar] <= 0:
					del d[stChar]
				start += 1
			if len(d) == k:
				longest = max(longest, end - start + 1)
		return longest


class Solution:

	def longestKSubstr(self, s, k):
		i = 0
		j = 0
		d = {}
		maxi = -1
		while j < len(s):
			if s[j] not in d.keys():
				d[s[j]] = 1
			else:
				d[s[j]] += 1
			if len(d) < k:
				j += 1
			elif len(d) == k:
				maxi = max(maxi, j - i + 1)
				j += 1
			elif len(d) > k:
				while len(d) > k:
					d[s[i]] -= 1
					if d[s[i]] == 0:
						del d[s[i]]
					i += 1
				j += 1
		return maxi


class Solution:

	def longestKSubstr(self, s, k):
		mx = -1
		(i, j) = (0, 0)
		tmp = {}
		while j < len(s):
			tmp[s[j]] = 1 + tmp.get(s[j], 0)
			if len(tmp) < k:
				j += 1
			elif len(tmp) == k:
				mx = max(mx, j - i + 1)
				j += 1
			elif len(tmp) > k:
				while len(tmp) > k:
					tmp[s[i]] -= 1
					if tmp[s[i]] == 0:
						del tmp[s[i]]
					i += 1
				j += 1
		return mx


from collections import defaultdict

class Solution:

	def longestKSubstr(self, s, k):
		if k > len(s):
			return -1
		d = defaultdict(int)
		(l, r, o, counter) = (0, 0, -1, 0)
		while r < len(s):
			if d[s[r]] == 0:
				counter += 1
			d[s[r]] += 1
			while counter > k:
				if d[s[l]] == 1:
					counter -= 1
				d[s[l]] -= 1
				l += 1
			if counter == k:
				o = max(o, r - l + 1)
			r += 1
		return o


class Solution:

	def longestKSubstr(self, s, k):
		i = 0
		j = 0
		m = -1
		map = {}
		if len(s) < k:
			return -1
		while j < len(s):
			if s[j] not in map:
				map[s[j]] = 1
			else:
				map[s[j]] += 1
			if len(map) < k:
				j += 1
			elif len(map) == k:
				m = max(m, j - i + 1)
				j += 1
			elif len(map) > k:
				while len(map) > k:
					map[s[i]] -= 1
					if map[s[i]] == 0:
						del map[s[i]]
					i += 1
				j += 1
		return m


class Solution:

	def longestKSubstr(self, s, k):
		characterSet = {}
		start = 0
		result = ''
		i = 0
		while i < len(s):
			if characterSet.get(s[i]) is not None:
				characterSet[s[i]] += 1
			elif len(characterSet) == k:
				if i - start > len(result):
					result = s[start:i]
				characterSet[s[start]] -= 1
				if characterSet[s[start]] == 0:
					del characterSet[s[start]]
				start += 1
				i -= 1
			else:
				characterSet[s[i]] = 1
			i += 1
		if i - start > len(result) and len(characterSet) == k:
			result = s[start:i]
		return len(result) if result else -1


class Solution:

	def longestKSubstr(self, s, k):
		if len(s) < k:
			return -1
		l = 0
		D = {s[l]: 1}
		ans = -1
		for r in range(1, len(s)):
			D[s[r]] = 1 + D.get(s[r], 0)
			if len(D) > k:
				while len(D) > k and l <= r:
					D[s[l]] = D[s[l]] - 1
					if D[s[l]] == 0:
						D.pop(s[l])
					l += 1
			if len(D) == k:
				ans = max(ans, r - l + 1)
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		dic = {}
		maxi = -10 ** 9
		c = 0
		start = 0
		mini = -10 ** 9
		for i in range(len(s)):
			if s[i] in dic:
				dic[s[i]] += 1
			else:
				dic[s[i]] = 1
				c += 1
			if c == k:
				maxi = max(maxi, i - start + 1)
			elif c > k:
				while start < i:
					dic[s[start]] -= 1
					start += 1
					if dic[s[start - 1]] == 0:
						dic.pop(s[start - 1])
						break
				maxi = max(maxi, i - start + 1)
				c -= 1
		if maxi == -10 ** 9:
			return -1
		return maxi


class Solution:

	def longestKSubstr(self, s, k):
		count = 0
		l = 0
		r = 0
		arr = {}
		maxx = 0
		for i in range(len(s)):
			if s[i] not in arr:
				count += 1
				arr[s[i]] = 1
			else:
				arr[s[i]] += 1
			if count > k:
				temp = l
				while l < r:
					arr[s[l]] -= 1
					l += 1
					if arr[s[l - 1]] == 0:
						break
				if l != temp:
					arr.pop(s[l - 1])
					count -= 1
				else:
					arr.pop(s[l])
					count -= 1
					l += 1
			if len(s[l:r + 1]) > maxx and count == k:
				maxx = len(s[l:r + 1])
			r += 1
		if maxx == 0:
			return -1
		return maxx


class Solution:

	def longestKSubstr(self, s, k):
		count = 0
		l = 0
		r = 0
		arr = {}
		temp = -1
		maxx = 0
		while r < len(s):
			if s[r] not in arr:
				count += 1
				arr[s[r]] = 1
			elif r != temp1:
				arr[s[r]] += 1
			if count > k:
				temp = l
				while l < r:
					arr[s[l]] -= 1
					l += 1
					if arr[s[l - 1]] == 0:
						break
				if l != temp:
					arr.pop(s[l - 1])
					count -= 1
				else:
					arr.pop(s[l])
					count -= 1
					l += 1
				if len(s[l:r + 1]) > maxx and count == k:
					maxx = len(s[l:r + 1])
			else:
				if len(s[l:r + 1]) > maxx and count == k:
					maxx = len(s[l:r + 1])
				temp1 = r
			r += 1
		if maxx == 0:
			return -1
		return maxx


class Solution:

	def longestKSubstr(self, s, k):
		map = {}
		left = 0
		maxLength = -1
		for right in range(len(s)):
			ch = s[right]
			map[ch] = map.get(ch, 0) + 1
			if len(map) == k:
				maxLength = max(maxLength, right - left + 1)
			while len(map) > k:
				left_char = s[left]
				map[left_char] -= 1
				if map[left_char] == 0:
					del map[left_char]
				left += 1
		return maxLength


class Solution:

	def longestKSubstr(self, s, k):
		d = {}
		i = 0
		j = 0
		maxl = 0
		while j < len(s):
			if s[j] in d:
				d[s[j]] = d[s[j]] + 1
			else:
				d[s[j]] = 1
			if len(d) < k:
				j = j + 1
			elif len(d) == k:
				if j - i + 1 > maxl:
					maxl = j - i + 1
				j = j + 1
			else:
				while len(d) > k:
					d[s[i]] = d[s[i]] - 1
					if d[s[i]] == 0:
						del d[s[i]]
					i = i + 1
				j = j + 1
		if maxl == 0:
			return -1
		return maxl


class Solution:

	def longestKSubstr(self, s, k):
		(i, j) = (0, 0)
		freq = {}
		ans = -1
		while j < len(s):
			if s[j] in freq:
				freq[s[j]] += 1
			else:
				freq[s[j]] = 1
			if len(freq) < k:
				j += 1
			elif len(freq) == k:
				ans = max(ans, j - i + 1)
				j += 1
			else:
				while len(freq) > k:
					freq[s[i]] -= 1
					if freq[s[i]] == 0:
						del freq[s[i]]
					i += 1
				j += 1
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		hashmap = {}
		for i in s:
			hashmap[i] = 1 + hashmap.get(i, 0)
		if len(hashmap) < k:
			return -1
		windowstart = 0
		hashtable = {}
		length = 0
		for windowend in range(len(s)):
			if s[windowend] not in hashtable:
				hashtable[s[windowend]] = 0
			hashtable[s[windowend]] += 1
			while len(hashtable) > k:
				hashtable[s[windowstart]] -= 1
				if hashtable[s[windowstart]] == 0:
					del hashtable[s[windowstart]]
				windowstart += 1
			length = max(length, windowend - windowstart + 1)
		return length


class Solution:

	def longestKSubstr(self, s, k):
		d = {}
		i = 0
		answer = 0
		for j in range(len(s)):
			d[s[j]] = d.get(s[j], 0) + 1
			if len(d) < k:
				pass
			elif len(d) == k:
				answer = max(answer, j - i + 1)
			elif len(d) > k:
				while len(d) > k and i <= j:
					d[s[i]] -= 1
					if d[s[i]] == 0:
						del d[s[i]]
					i += 1
		return answer if answer > 0 else -1


class Solution:

	def longestKSubstr(self, s, k):
		(pt1, pt2, ct, max_len) = (0, 0, 0, 0)
		hash_map = {}
		while pt2 < len(s):
			if s[pt2] in hash_map:
				hash_map[s[pt2]] += 1
			else:
				hash_map[s[pt2]] = 1
				ct += 1
			while ct > k and pt1 <= pt2:
				hash_map[s[pt1]] -= 1
				if hash_map[s[pt1]] == 0:
					del hash_map[s[pt1]]
					ct -= 1
				pt1 += 1
			if ct == k:
				max_len = max(max_len, pt2 - pt1 + 1)
			pt2 += 1
		if max_len == 0:
			return -1
		return max_len


class Solution:

	def longestKSubstr(self, s, k):
		i = -1
		j = -1
		left = 0
		right = 0
		hm = {}
		while right < len(s):
			if s[right] not in hm:
				hm[s[right]] = 1
			else:
				hm[s[right]] += 1
			while left <= right and len(hm) > k:
				hm[s[left]] -= 1
				if hm[s[left]] == 0:
					del hm[s[left]]
				left += 1
			if len(hm) == k:
				if i == -1 and j == -1:
					i = left
					j = right
				elif j - i < right - left:
					i = left
					j = right
			right += 1
		if i == -1 and j == -1:
			return -1
		return len(s[i:j + 1])


class Solution:

	def longestKSubstr(self, s, k):
		char_count = {}
		head = 0
		current = 0
		ans = -1
		for char in s:
			if char in char_count:
				char_count[char] += 1
			else:
				char_count[char] = 1
			length = len(char_count)
			if length == k:
				if ans < sum(char_count.values()):
					ans = sum(char_count.values())
			elif length < k:
				continue
			else:
				while len(char_count) > k:
					char_count[s[head]] -= 1
					if char_count[s[head]] == 0:
						char_count.pop(s[head])
					head += 1
				if len(char_count) == k:
					if ans < sum(char_count.values()):
						ans = sum(char_count.values())
			current += 1
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		i = 0
		j = 0
		n = len(s)
		unique = {}
		longest = 0
		while j < n:
			unique[s[j]] = unique.get(s[j], 0) + 1
			if len(unique) == k:
				longest = max(longest, j - i + 1)
			elif len(unique) > k:
				while len(unique) > k:
					unique[s[i]] = unique.get(s[i]) - 1
					if unique[s[i]] == 0:
						del unique[s[i]]
					i += 1
			j += 1
		if longest != 0:
			return longest
		return -1


from collections import defaultdict

class Solution:

	def longestKSubstr(self, s, k):
		dic = defaultdict(lambda : 0)
		i = j = 0
		ans = -1
		n = len(s)
		while j < n:
			dic[s[j]] += 1
			if len(dic) < k:
				j += 1
			elif len(dic) == k:
				ans = max(ans, j - i + 1)
				j += 1
			elif len(dic) > k:
				while len(dic) > k:
					dic[s[i]] -= 1
					if dic[s[i]] == 0:
						del dic[s[i]]
					i += 1
				j += 1
		return ans


import math

class Solution:

	def longestKSubstr(self, s, k):
		hashMap = {}
		windowSize = -math.inf
		windowStart = 0
		for windowEnd in range(len(s)):
			if s[windowEnd] not in hashMap:
				hashMap[s[windowEnd]] = 0
			hashMap[s[windowEnd]] += 1
			while len(hashMap) > k:
				hashMap[s[windowStart]] -= 1
				if hashMap[s[windowStart]] == 0:
					del hashMap[s[windowStart]]
				windowStart += 1
			windowSize = max(windowSize, windowEnd - windowStart + 1)
		return windowSize if len(hashMap) == k else -1


class Solution:

	def longestKSubstr(self, s, k):
		hm = {}
		i = 0
		result = -1
		for (j, val) in enumerate(s):
			hm[val] = hm.get(val, 0) + 1
			while len(hm) > k:
				hm[s[i]] -= 1
				if hm[s[i]] == 0:
					del hm[s[i]]
				i += 1
			if len(hm) == k:
				result = max(result, j - i + 1)
		return result


class Solution:

	def longestKSubstr(self, s, k):
		left = right = 0
		res = -1
		dic = {}
		while right < len(s):
			dic[s[right]] = dic.get(s[right], 0) + 1
			if len(dic) < k:
				right += 1
			elif len(dic) == k:
				res = max(res, right - left + 1)
				right += 1
			else:
				while len(dic) > k:
					dic[s[left]] -= 1
					if dic[s[left]] == 0:
						dic.pop(s[left])
					left += 1
				right += 1
		return res


class Solution:

	def longestKSubstr(self, s, k):
		(window_start, hash_map, max_len) = (0, {}, 0)
		for window_end in range(len(s)):
			hash_map[s[window_end]] = 1 + hash_map.get(s[window_end], 0)
			while len(hash_map) > k:
				hash_map[s[window_start]] -= 1
				if hash_map[s[window_start]] == 0:
					del hash_map[s[window_start]]
				window_start += 1
			max_len = max(max_len, window_end - window_start + 1)
		return -1 if len(hash_map) < k else max_len


class Solution:

	def longestKSubstr(self, s, k):
		maxi = -1
		d = dict()
		distinct = 0
		left = 0
		for i in range(len(s)):
			right = i
			if s[i] in d:
				d[s[i]] += 1
			else:
				d[s[i]] = 1
				distinct += 1
			if distinct == k:
				maxi = max(maxi, right - left + 1)
			elif distinct > k:
				while distinct > k:
					d[s[left]] -= 1
					if d[s[left]] == 0:
						del d[s[left]]
						distinct -= 1
					left += 1
		return maxi


from collections import defaultdict

class Solution:

	def longestKSubstr(self, s, k):
		i = j = 0
		d = defaultdict(int)
		total = 0
		res = 0
		for j in range(len(s)):
			d[s[j]] += 1
			total += 1
			while len(d) > k:
				d[s[i]] -= 1
				if d[s[i]] == 0:
					d.pop(s[i])
				i += 1
				total -= 1
			if len(d) == k:
				res = max(res, total)
		if res == 0:
			return -1
		return res


class Solution:

	def longestKSubstr(self, s, k):
		n = len(s)
		distinct = 0
		length = 0
		letters = {}
		(i, j) = (0, 0)
		while j < n:
			if s[j] in letters:
				letters[s[j]] += 1
			else:
				letters[s[j]] = 1
			distinct = len(letters)
			if distinct == k:
				length = max(length, j - i + 1)
			while distinct > k:
				letters[s[i]] -= 1
				if letters[s[i]] == 0:
					del letters[s[i]]
				distinct = len(letters)
				i += 1
			j += 1
		return length if length != 0 else -1


class Solution:

	def longestKSubstr(self, s, k):
		(wstart, wend) = (0, 0)
		d = {}
		ans = -1
		while wend < len(s):
			d[s[wend]] = d.get(s[wend], 0) + 1
			if len(d) == k:
				ans = max(ans, wend - wstart + 1)
			if len(d) > k:
				while len(d) > k:
					d[s[wstart]] -= 1
					if d[s[wstart]] == 0:
						del d[s[wstart]]
					wstart += 1
			wend += 1
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		freq = {}
		(i, j) = (0, 0)
		ans = -1
		longest = ''
		while j < len(s):
			freq[s[j]] = 1 + freq.get(s[j], 0)
			while len(freq) > k:
				freq[s[i]] -= 1
				if freq[s[i]] == 0:
					del freq[s[i]]
				i += 1
			if len(freq) == k and j - i + 1 > len(longest):
				longest = s[i:j + 1]
				ans = max(ans, j - i + 1)
			j += 1
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		if not s:
			return 0
		char_count = {}
		num = -1
		left = 0
		for i in range(len(s)):
			char_count[s[i]] = char_count.get(s[i], 0) + 1
			while len(char_count) > k:
				char_count[s[left]] -= 1
				if char_count[s[left]] == 0:
					char_count.pop(s[left])
				left += 1
			if len(char_count) == k:
				num = max(num, i - left + 1)
		return num


from collections import defaultdict

class Solution:

	def longestKSubstr(self, st, k):
		d = defaultdict(int)
		(s, e, res) = (0, 0, -1)
		n = len(st)
		while e < n:
			d[st[e]] += 1
			if len(d) == k:
				res = max(res, e - s + 1)
				e += 1
			elif len(d) < k:
				e += 1
			else:
				while len(d) > k:
					d[st[s]] -= 1
					if d[st[s]] == 0:
						del d[st[s]]
					s += 1
				e += 1
		return res


class Solution:

	def longestKSubstr(self, s, k):
		substrs = []
		substr = ''
		chars = {}
		for c in s:
			substr += c
			if c in chars.keys():
				chars[c] += 1
			else:
				chars[c] = 1
			if len(chars) == k:
				substrs.append(substr)
				continue
			while len(chars) > k:
				if chars[substr[0]] == 1:
					chars.pop(substr[0])
				else:
					chars[substr[0]] -= 1
				substr = substr[1:]
		if len(chars) == k:
			substrs.append(substr)
		res = max([len(ss) for ss in substrs]) if substrs else -1
		return res


class Solution:

	def longestKSubstr(self, s, k):
		map = {}
		end = 0
		start = 0
		found = False
		maxLen = 0
		while end < len(s):
			while len(map) <= k and end < len(s):
				if s[end] not in map:
					map[s[end]] = 0
				map[s[end]] += 1
				end += 1
			while len(map) > k and start < end:
				if maxLen < end - start - 1:
					maxLen = end - start - 1
					found = True
				if s[start] in map:
					if map[s[start]] == 1:
						del map[s[start]]
					else:
						map[s[start]] -= 1
				start += 1
		if len(map) == k and end - start > maxLen:
			maxLen = end - start
			found = True
		if found == True:
			return maxLen
		else:
			return -1


class Solution:

	def longestKSubstr(self, s, k):
		mp = dict()
		(i, j, ans) = (0, 0, -1)
		n = len(s)
		while j < n:
			if s[j] in mp:
				mp[s[j]] += 1
			else:
				mp[s[j]] = 1
			if len(mp) < k:
				j += 1
			if len(mp) == k:
				ans = max(ans, j - i + 1)
				j += 1
			elif len(mp) > k:
				while len(mp) > k:
					mp[s[i]] -= 1
					if mp[s[i]] == 0:
						mp.pop(s[i])
					i += 1
				j += 1
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		i = 0
		j = 0
		dic = {}
		ans = -1
		while j < len(s):
			if s[j] not in dic:
				dic[s[j]] = 1
			else:
				dic[s[j]] += 1
			if len(dic) < k:
				j += 1
			elif len(dic) == k:
				ans = max(j - i + 1, ans)
				j += 1
			elif len(dic) > k:
				while len(dic) > k:
					if s[i] in dic:
						dic[s[i]] -= 1
						if dic[s[i]] == 0:
							dic.pop(s[i])
					i += 1
				j += 1
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		n = len(s)
		dic = {}
		ans = -1
		i = 0
		j = 0
		while j < n:
			if s[j] in dic:
				dic[s[j]] += 1
			else:
				dic[s[j]] = 1
			if len(dic) > k:
				ans = max(ans, j - i)
				while len(dic) > k:
					dic[s[i]] -= 1
					if dic[s[i]] == 0:
						del dic[s[i]]
					i += 1
			j += 1
		if len(dic) == k:
			ans = max(ans, j - i)
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		return self.helper(s, k)

	def helper(self, s, k):
		(i, j, ans) = (0, 0, -1)
		state = {}
		N = len(s)
		for j in range(N):
			state[s[j]] = 1 + state.get(s[j], 0)
			while len(state) > k:
				state[s[i]] -= 1
				if state[s[i]] == 0:
					state.pop(s[i])
				i += 1
			if len(state) == k:
				ans = max(ans, j - i + 1)
		return ans


class Solution:

	def longestKSubstr(self, a, k):
		(i, j) = (0, 0)
		s = {}
		maxi = 0
		n = len(a)
		while j < n:
			if a[j] in s:
				s[a[j]] += 1
			else:
				s[a[j]] = 1
			j += 1
			while len(s) > k:
				s[a[i]] -= 1
				if s[a[i]] == 0:
					del s[a[i]]
				i += 1
			maxi = max(maxi, j - i)
		if len(s) < k:
			return -1
		else:
			return maxi


class Solution:

	def longestKSubstr(self, s, k):
		n = len(s)
		hashmap = {}
		(l, r) = (0, 0)
		res = 0
		while r < n:
			while len(hashmap) > k:
				hashmap[s[l]] -= 1
				if hashmap[s[l]] == 0:
					del hashmap[s[l]]
				l += 1
			hashmap[s[r]] = 1 + hashmap.get(s[r], 0)
			if len(hashmap) == k:
				res = max(res, r - l + 1)
			r += 1
		return res if res != 0 else -1


class Solution:

	def longestKSubstr(self, s, k):
		(a, b) = longest_k_substring(s, k)
		return b
from collections import defaultdict

def longest_k_substring(s, k):
	substring_begin = substring_end = 0
	distinct_chars = set()
	freq = defaultdict(lambda : 0)
	low = high = 0
	while high < len(s):
		distinct_chars.add(s[high])
		freq[s[high]] += 1
		while len(distinct_chars) > k:
			leftmost_char = s[low]
			freq[leftmost_char] -= 1
			if freq[leftmost_char] == 0:
				distinct_chars.remove(leftmost_char)
			low += 1
		if substring_end - substring_begin < high - low:
			substring_end = high
			substring_begin = low
		high += 1
	substring = s[substring_begin:substring_end + 1]
	if len(set(substring)) == k:
		return (substring, len(substring))
	return ('', -1)


class Solution:

	def longestKSubstr(self, s, k):
		di = {}
		i = 0
		j = 0
		n = len(s)
		maxLen = 0
		while j < n:
			if s[j] not in di:
				di[s[j]] = 1
			else:
				di[s[j]] += 1
			if len(di) < k:
				j += 1
			elif len(di) == k:
				maxLen = max(maxLen, j - i + 1)
				j += 1
			elif len(di) > k:
				while len(di) > k:
					di[s[i]] -= 1
					if di[s[i]] == 0:
						del di[s[i]]
					i += 1
				if len(di) == k:
					maxLen = max(maxLen, j - i + 1)
					j += 1
		if maxLen == 0:
			return -1
		return maxLen


class Solution:

	def longestKSubstr(self, S, K):
		ans = float('-inf')
		left = 0
		freq = {}
		for right in range(len(S)):
			freq[S[right]] = freq.get(S[right], 0) + 1
			while len(freq) > k:
				freq[S[left]] -= 1
				if freq[S[left]] == 0:
					del freq[S[left]]
				left += 1
			if len(freq) == k:
				ans = max(ans, right - left + 1)
		return ans if ans != float('-inf') else -1


class Solution:

	def longestKSubstr(self, s, k):
		n = len(s)
		a = s
		i = 0
		f = {}
		(l, o) = (0, 0)
		i = 0
		j = 0
		ans = -1
		while i < n and j < n:
			if a[j] not in f or f[a[j]] == 0:
				f[a[j]] = 1
				o += 1
			else:
				f[a[j]] += 1
			l += 1
			if o == k:
				ans = max(l, ans)
			elif o > k:
				while i < j:
					f[a[i]] -= 1
					l -= 1
					if f[a[i]] == 0:
						i += 1
						break
					i += 1
				o -= 1
			j += 1
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		m = {}
		for x in s:
			m[x] = 0
		uniq = 0
		i = 0
		j = 0
		res = 0
		n = len(s)
		while j < n:
			while j < n:
				if m[s[j]] == 0:
					uniq += 1
				m[s[j]] += 1
				if uniq > k:
					break
				j += 1
			if uniq >= k:
				res = max(res, j - i)
			if j == n:
				break
			while i < n:
				if m[s[i]] == 1:
					uniq -= 1
				m[s[i]] -= 1
				if uniq == k:
					break
				i += 1
			i += 1
			j += 1
		if res == 0:
			return -1
		return res


class Solution:

	def longestKSubstr(self, s, k):
		d = {}
		i = 0
		j = 0
		max1 = -1
		while i < len(s):
			if s[i] in d:
				d[s[i]] += 1
			else:
				if len(d) == k:
					max1 = max(max1, i - j)
					while len(d) == k:
						if d[s[j]] == 1:
							del d[s[j]]
						else:
							d[s[j]] -= 1
						j += 1
				d[s[i]] = 1
			i += 1
		if len(d) < k or len(d) > k:
			return max1
		return max(max1, i - j)


class Solution:

	def longestKSubstr(self, s, k):
		n = len(s)
		(i, j) = (0, 0)
		maxi = -1
		dicti = {}
		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:
				maxi = max(maxi, j - i + 1)
				j += 1
			elif len(dicti) > k:
				while len(dicti) > k:
					if s[i] in dicti:
						dicti[s[i]] -= 1
						if dicti[s[i]] == 0:
							del dicti[s[i]]
					i += 1
				j += 1
		return maxi


class Solution:

	def longestKSubstr(self, s, k):
		d = {}
		l = len(s)
		j = 0
		mx = -1
		for i in range(l):
			if s[i] not in d:
				d[s[i]] = 1
			else:
				d[s[i]] = d[s[i]] + 1
			while len(d) > k:
				d[s[j]] = d[s[j]] - 1
				if d[s[j]] <= 0:
					del d[s[j]]
				j += 1
			if len(d) == k:
				mx = max(mx, i - j + 1)
		return mx


class Solution:

	def longestKSubstr(self, s, k):
		hmap = {}
		start = 0
		res = 0
		for end in range(len(s)):
			if s[end] not in hmap:
				hmap[s[end]] = 0
			hmap[s[end]] += 1
			while len(hmap) > k:
				hmap[s[start]] -= 1
				if hmap[s[start]] == 0:
					del hmap[s[start]]
				start += 1
			if len(hmap) == k:
				res = max(res, end - start + 1)
		return res if res != 0 else -1


class Solution:

	def longestKSubstr(self, s, k):
		i = 0
		j = 0
		d = {}
		res = -1
		n = len(s)
		while i < n:
			if s[i] not in d:
				if len(d) == k:
					while len(d) == k:
						d[s[j]] -= 1
						if d[s[j]] == 0:
							del d[s[j]]
						j += 1
			d[s[i]] = d.get(s[i], 0) + 1
			if len(d) == k:
				res = max(res, i + 1 - j)
			i += 1
		return res


class Solution:

	def longestKSubstr(self, s, k):
		i = 0
		result = -1
		mapp = dict()
		for (j, v) in enumerate(s):
			mapp[v] = mapp.get(v, 0) + 1
			if len(mapp) == k:
				total = 0
				for val in mapp.values():
					total += val
				result = max(result, total)
			while len(mapp) > k:
				mapp[s[i]] -= 1
				if mapp[s[i]] == 0:
					del mapp[s[i]]
				i += 1
		return result


class Solution:

	def longestKSubstr(self, s, k):
		i = 0
		n = len(s)
		j = 0
		res = ''
		maxres = 0
		d = {}
		while j < n:
			res += s[j]
			if s[j] in d:
				d[s[j]] += 1
			else:
				d[s[j]] = 1
			if len(d) > k:
				while len(d) > k:
					d[s[i]] -= 1
					if d[s[i]] == 0:
						d.pop(s[i])
					res = res[1:]
					i += 1
			elif len(d) == k:
				maxres = max(maxres, len(res))
			j += 1
		if maxres > 0:
			return maxres
		return -1


class Solution:

	def longestKSubstr(self, s, k):
		occurences = {}
		count = k
		l = 0
		r = 0
		n = len(s)
		maxLen = -1
		while r < n:
			occurences[s[r]] = occurences.get(s[r], 0) + 1
			if occurences[s[r]] == 1:
				count -= 1
			if count == 0:
				maxLen = max(maxLen, r - l + 1)
			elif count < 0:
				while count < 0:
					occurences[s[l]] -= 1
					if occurences[s[l]] == 0:
						count += 1
					l += 1
			r += 1
		return maxLen


class Solution:

	def longestKSubstr(self, s, k):
		ans = -1
		ws = 0
		d = {}
		for i in range(len(s)):
			c = s[i]
			if c in d:
				d[c] += 1
			else:
				d[c] = 1
			while len(d) > k:
				a = s[ws]
				d[a] -= 1
				if d[a] == 0:
					del d[a]
				ws += 1
			if len(d) == k:
				ans = max(ans, i - ws + 1)
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		map = {}
		start = 0
		end = 0
		maxlen = -1
		while end < len(s):
			map[s[end]] = map.get(s[end], 0) + 1
			if len(map) == k:
				maxlen = max(maxlen, end - start + 1)
			while len(map) > k:
				map[s[start]] -= 1
				if map[s[start]] == 0:
					map.pop(s[start])
				start += 1
			end += 1
		return maxlen


class Solution:

	def uniqChars(self, s):
		map = {}
		for i in s:
			map[i] = True
		return len(map.keys())

	def longestKSubstr(self, s, k):
		freq = {}
		(i, j) = (0, 1)
		if self.uniqChars(s) < k:
			return -1
		freq[s[0]] = 1
		mxLen = 1
		uniq = 1
		while i < len(s) and j < len(s):
			if freq.get(s[j], 0) == 0:
				uniq += 1
			freq[s[j]] = freq.get(s[j], 0) + 1
			if uniq == k:
				mxLen = max(mxLen, j - i + 1)
			elif uniq > k:
				while uniq > k:
					freq[s[i]] -= 1
					if freq[s[i]] == 0:
						uniq -= 1
					i += 1
			j += 1
		return mxLen


class Solution:

	def longestKSubstr(self, s, k):
		d = {}
		ws = 0
		ans = -1
		for i in range(len(s)):
			d[s[i]] = d.get(s[i], 0) + 1
			while len(d) > k:
				d[s[ws]] -= 1
				if d[s[ws]] == 0:
					del d[s[ws]]
				ws += 1
			if len(d) == k:
				ans = max(ans, i - ws + 1)
		return ans


class Solution:

	def longestKSubstr(self, s, k):
		if len(s) < k or len(set(s)) < k:
			return -1
		map1 = {}
		start = 0
		(maxlength, curr) = (0, -1)
		for end in range(len(s)):
			if s[end] not in map1:
				map1[s[end]] = 0
			map1[s[end]] += 1
			while len(map1) > k:
				map1[s[start]] -= 1
				if map1[s[start]] <= 0:
					del map1[s[start]]
				start += 1
			curr = max(curr, end - start + 1)
		return curr


class Solution:

	def longestKSubstr(self, s, k):
		(i, j) = (0, 0)
		d = {}
		n = len(s)
		l = -1
		while j < n:
			d[s[j]] = d.get(s[j], 0) + 1
			if len(d) == k:
				l = max(l, j - i + 1)
			if len(d) > k:
				while len(d) > k:
					d[s[i]] -= 1
					if d[s[i]] == 0:
						d.pop(s[i])
					i += 1
				if len(d) == k:
					l = max(l, j - i + 1)
			j += 1
		return l


class Solution:

	def longestKSubstr(self, s, k):
		i = 0
		j = 0
		m = {}
		maxi = -1
		while j < len(s):
			m[s[j]] = 1 + m.get(s[j], 0)
			if len(m) < k:
				j += 1
			elif len(m) == k:
				maxi = max(maxi, j - i + 1)
				j += 1
			else:
				while len(m) > k:
					if m[s[i]] == 1:
						del m[s[i]]
					else:
						m[s[i]] -= 1
					i += 1
				j += 1
		return maxi


class Solution:

	def longestKSubstr(self, s, k):
		ans = float('-inf')
		curr = 0
		startWindow = 0
		mp = {}
		for endWindow in range(len(s)):
			if s[endWindow] not in mp:
				mp[s[endWindow]] = 1
			else:
				mp[s[endWindow]] += 1
			while len(mp) > k:
				mp[s[startWindow]] -= 1
				if mp[s[startWindow]] == 0:
					mp.pop(s[startWindow])
				startWindow += 1
			ans = max(ans, endWindow + 1 - startWindow)
		if len(mp) != k:
			return -1
		return ans


from collections import defaultdict

class Solution:

	def longestKSubstr(self, s, k):
		hashmap = defaultdict(int)
		left = 0
		res = 0
		right = 0
		while left <= right and right < len(s):
			hashmap[s[right]] += 1
			if len(hashmap) == k:
				res = max(res, right - left + 1)
			while len(hashmap) > k:
				hashmap[s[left]] -= 1
				if hashmap[s[left]] == 0:
					del hashmap[s[left]]
				left += 1
			right += 1
		if not res:
			return -1
		return res


class Solution:

	def longestKSubstr(self, s, k):
		left = 0
		freq = {}
		res = 0
		for (right, c) in enumerate(s):
			freq[c] = freq.get(c, 0) + 1
			if len(freq) == k:
				res = max(res, right - left + 1)
			while len(freq) > k:
				freq[s[left]] -= 1
				if not freq[s[left]]:
					del freq[s[left]]
				left += 1
		return res if res else -1


class Solution:

	def longestKSubstr(self, s, k):
		d = {}
		for i in range(len(s)):
			if s[i] in d:
				d[s[i]] += 1
			else:
				d[s[i]] = 1
		if len(d) < k:
			return -1
		m = {}
		j = 0
		ans = 0
		for i in range(len(s)):
			if s[i] in m:
				m[s[i]] += 1
			else:
				m[s[i]] = 1
			while len(m) > k:
				m[s[j]] = m[s[j]] - 1
				if m[s[j]] == 0:
					del m[s[j]]
				j = j + 1
			ans = max(ans, i - j + 1)
		return ans


from collections import defaultdict

class Solution:

	def longestKSubstr(self, s, k):
		count = defaultdict(int)
		letters = 0
		i = 0
		j = 0
		res = 0
		for j in range(len(s)):
			count[s[j]] += 1
			if count[s[j]] == 1:
				letters += 1
			while letters > k:
				count[s[i]] -= 1
				if count[s[i]] == 0:
					letters -= 1
				i += 1
			if letters == k:
				res = max(res, j - i + 1)
		return res if res > 0 else -1


class Solution:

	def longestKSubstr(self, s, k):
		count = {}
		letters = 0
		i = 0
		j = 0
		res = 0
		for j in range(len(s)):
			count[s[j]] = 1 + count.get(s[j], 0)
			if count[s[j]] == 1:
				letters += 1
			while letters > k:
				count[s[i]] -= 1
				if count[s[i]] == 0:
					letters -= 1
				i += 1
			if letters == k:
				res = max(res, j - i + 1)
		return res if res > 0 else -1


class Solution:

	def longestKSubstr(self, s, k):
		d = {}
		ans = -1
		(p1, p2, n) = (0, 0, len(s))
		b = False
		while p2 < n:
			if s[p2] in d:
				d[s[p2]] += 1
			else:
				d[s[p2]] = 1
			while len(d) > k and p1 <= p2:
				d[s[p1]] -= 1
				if d[s[p1]] == 0:
					del d[s[p1]]
				p1 += 1
				b = True
			ans = max(ans, p2 - p1 + 1)
			p2 += 1
		if b or len(d) == k:
			return ans
		return -1


class Solution:

	def longestKSubstr(self, s, k):
		b = set()
		for i in s:
			b.add(i)
		if len(b) < k:
			return -1
		(l, r, res) = (0, 0, 0)
		map_ = {}
		while r < len(s):
			map_[s[r]] = map_.get(s[r], 0) + 1
			while len(map_) > k:
				charAtFront = s[l]
				map_[s[l]] -= 1
				if map_[s[l]] == 0:
					map_.pop(s[l])
				l += 1
			res = max(res, r - l + 1)
			r += 1
		return res