Given a String S consisting only lowercase alphabets and an integer K. Find the count of all substrings of length K which have exactly K-1 distinct characters. 
 
Example 1:
Input:
S = "abcc"
K = 2
Output:
1
Explanation:
Possible substrings of length K = 2 are
ab : 2 distinct characters
bc : 2 distinct characters
cc : 1 distinct character
Only one valid substring exists {"cc"}. 
Example 2:
Input:
S = "aabab"
K = 3
Output :
3
Explanation:
Possible substrings of length K = 3 are
aab : 2 distinct characters
aba : 2 distinct characters
bab : 2 distinct characters.
All of these Substrings are a possible answer,
so the count is 3.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countOfSubstrings() which takes a String S and an integer K as input and returns the count of substrings of length K having K-1 distinct characters.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(constant)
Constraints:
1 ≤ K ≤ |S| ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def countOfSubstrings(self, S, K):

        # code here 

Solutions:
class Solution:

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


import collections

class Solution:

	def countOfSubstrings(self, S, K):
		freq_each = collections.defaultdict(int)
		l = 1
		r = j = sol = 0
		while r < K:
			freq_each[S[r]] += 1
			r += 1
		if len(freq_each) == K - 1:
			sol += 1
		while r < len(S):
			freq_each[S[r]] += 1
			freq_each[S[l - 1]] -= 1
			if freq_each[S[l - 1]] == 0:
				del freq_each[S[l - 1]]
			if len(freq_each) == K - 1:
				sol += 1
			r += 1
			l += 1
		return sol


class Solution:

	def countOfSubstrings(self, S, K):
		count = 0
		dic = {}
		(i, j) = (0, 0)
		while j < len(S):
			if S[j] in dic:
				dic[S[j]] += 1
			else:
				dic[S[j]] = 1
			if j - i + 1 == K:
				if len(dic) == K - 1:
					count += 1
			elif j - i + 1 > K:
				dic[S[i]] -= 1
				if dic[S[i]] == 0:
					del dic[S[i]]
				i += 1
				if len(dic) == K - 1:
					count += 1
			j += 1
		return count


class Solution:

	def countOfSubstrings(self, S, K):
		d = {}
		for i in S[:K]:
			d[i] = d.get(i, 0) + 1
		count = 0
		window = K
		slides = len(S) - window
		if len(d) == K - 1:
			count += 1
		for j in range(slides):
			Add = S[window]
			Sub = S[j]
			d[Add] = d.get(Add, 0) + 1
			d[Sub] -= 1
			if d.get(Sub) == 0:
				d.pop(Sub)
			if len(d) == K - 1:
				count += 1
			window += 1
		return count


from collections import Counter

class Solution:

	def countOfSubstrings(self, S, K):
		count = 0
		window = Counter(S[:K - 1])
		for i in range(K - 1, len(S)):
			window[S[i]] += 1
			if len(window) == K - 1:
				count += 1
			window[S[i - K + 1]] -= 1
			if window[S[i - K + 1]] == 0:
				del window[S[i - K + 1]]
		return count


class Solution:

	def countOfSubstrings(self, s, k):
		ans = 0
		left = 0
		right = 0
		freq = {}
		while right < len(S):
			freq[S[right]] = freq.get(S[right], 0) + 1
			while right - left + 1 > k:
				freq[S[left]] -= 1
				if freq[S[left]] == 0:
					del freq[S[left]]
				left += 1
			if right - left + 1 == k:
				if len(freq) == k - 1:
					ans += 1
			right += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		occurences = {}
		l = 0
		r = 0
		distinct = K - 1
		count = 0
		n = len(S)
		while r < n:
			occurences[S[r]] = occurences.get(S[r], 0) + 1
			if occurences[S[r]] == 1:
				distinct -= 1
			if r - l + 1 == K:
				if distinct == 0:
					count += 1
				occurences[S[l]] -= 1
				if occurences[S[l]] == 0:
					distinct += 1
				l += 1
			r += 1
		return count


from collections import defaultdict

class Solution:

	def countOfSubstrings(self, S, K):
		left = 0
		count = 0
		n = len(S)
		hmap = defaultdict(int)
		for right in range(0, n):
			if S[right] not in hmap:
				hmap[S[right]] = 1
			else:
				hmap[S[right]] += 1
			if right - left + 1 == K:
				if len(hmap) == K - 1:
					count += 1
			elif right - left + 1 > K:
				hmap[S[left]] -= 1
				if hmap[S[left]] == 0:
					del hmap[S[left]]
				left += 1
				if len(hmap) == K - 1:
					count += 1
		return count


from collections import defaultdict

class Solution:

	def countOfSubstrings(self, S, K):
		d = defaultdict(lambda : 0)
		l = 0
		for i in range(K):
			if S[i] not in d.keys():
				l += 1
			d[S[i]] += 1
		ans = 0
		if l == K - 1:
			ans += 1
		j = 0
		i = K
		while i < len(S):
			if S[i] not in d.keys() or d[S[i]] == 0:
				l += 1
			d[S[i]] += 1
			d[S[j]] -= 1
			if d[S[j]] == 0:
				l -= 1
			if l == K - 1:
				ans += 1
			i += 1
			j += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		k = K - 1
		s = S
		dict1 = {}
		count = 0
		j = 0
		for i in range(len(s)):
			if s[i] in dict1:
				dict1[s[i]] += 1
			else:
				dict1[s[i]] = 1
			while len(dict1) > k or sum(dict1.values()) > K:
				dict1[s[j]] -= 1
				if dict1[s[j]] == 0:
					del dict1[s[j]]
				j += 1
			if len(dict1) == k and sum(dict1.values()) == K:
				count += 1
		return count


class Solution:

	def countOfSubstrings(self, S, k):
		l = 0
		ans = 0
		map = [0] * 26
		for i in range(k):
			if map[ord(S[i]) - ord('a')] == 0:
				map[ord(S[i]) - ord('a')] = 1
				l += 1
			else:
				map[ord(S[i]) - ord('a')] += 1
		if k - 1 == l:
			ans += 1
		i = 0
		j = k
		while j < len(S):
			map[ord(S[i]) - ord('a')] -= 1
			if map[ord(S[i]) - ord('a')] == 0:
				l -= 1
			if map[ord(S[j]) - ord('a')] > 0:
				map[ord(S[j]) - ord('a')] += 1
			if map[ord(S[j]) - ord('a')] == 0:
				l += 1
				map[ord(S[j]) - ord('a')] += 1
			if k - 1 == l:
				ans += 1
			i += 1
			j += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		d = dict()
		count = 0
		i = 0
		j = 0
		while j < len(S):
			if S[j] not in d:
				d[S[j]] = 1
			else:
				d[S[j]] += 1
			if j - i + 1 == K:
				if len(d) == K - 1:
					count += 1
			elif j - i + 1 > K:
				d[S[i]] -= 1
				if d[S[i]] == 0:
					del d[S[i]]
				i += 1
				if j - i + 1 == K:
					if len(d) == K - 1:
						count += 1
			j += 1
		return count


class Solution:

	def countOfSubstrings(self, S, K):
		map1 = {}
		count = 0
		n = len(S)
		if K == 1 and len(S) < 2:
			return 0
		for i in range(K):
			if S[i] in map1:
				map1[S[i]] += 1
			else:
				map1[S[i]] = 1
		if len(map1) == K - 1:
			count += 1
		for i in range(K, n):
			if S[i] in map1:
				map1[S[i]] += 1
			else:
				map1[S[i]] = 1
			map1[S[i - K]] -= 1
			if map1[S[i - K]] == 0:
				map1.pop(S[i - K])
			if len(map1) == K - 1:
				count += 1
		return count


class Solution:

	def countOfSubstrings(self, S, K):
		count = 0
		dic = dict()
		(i, j) = (0, 0)
		while j < len(S):
			dic[S[j]] = dic.get(S[j], 0) + 1
			if j - i + 1 == K:
				if len(dic) == K - 1:
					count += 1
			elif j - i + 1 > K:
				dic[S[i]] -= 1
				if dic[S[i]] == 0:
					del dic[S[i]]
				i += 1
				if len(dic) == K - 1:
					count += 1
			j += 1
		return count


class Solution:

	def countOfSubstrings(self, s, k):
		ans = {}
		res = 0
		for i in range(k):
			ans[s[i]] = ans.get(s[i], 0) + 1
		if len(ans) == k - 1:
			res += 1
		for i in range(k, len(s)):
			ans[s[i - k]] -= 1
			if ans[s[i - k]] == 0:
				del ans[s[i - k]]
			ans[s[i]] = ans.get(s[i], 0) + 1
			if len(ans) == k - 1:
				res += 1
		return res


from collections import defaultdict

class Solution:

	def countOfSubstrings(self, S, K):
		n = len(S)
		d = defaultdict(lambda : 0)
		for i in range(K):
			d[S[i]] += 1
		count = int(len(d) == K - 1)
		for i in range(n - K):
			d[S[i + K]] += 1
			d[S[i]] -= 1
			if d[S[i]] == 0:
				del d[S[i]]
			count += len(d) == K - 1
		return count


class Solution:

	def countOfSubstrings(self, S, k):
		count = 0
		d = {}
		for x in S[:k]:
			if d.get(x) == None:
				d[x] = 0
			d[x] += 1
		count += len(d) == k - 1
		for x in range(1, len(S) - k + 1):
			rem = S[x - 1]
			add = S[x + k - 1]
			d[rem] -= 1
			if d[rem] == 0:
				del d[rem]
			if d.get(add) == None:
				d[add] = 0
			d[add] += 1
			count += len(d) == k - 1
		return count


class Solution:

	def countOfSubstrings(self, S, K):
		result = 0
		hash = {}
		for i in range(K):
			hash[S[i]] = hash.get(S[i], 0) + 1
		if len(hash) == K - 1:
			result += 1
		for i in range(K, len(S)):
			hash[S[i]] = hash.get(S[i], 0) + 1
			if hash[S[i - K]] == 1:
				hash.pop(S[i - K])
			else:
				hash[S[i - K]] -= 1
			if len(hash) == K - 1:
				result += 1
		return result


class Solution:

	def countOfSubstrings(self, s, k):
		c = 0
		d = dict()
		for i in range(0, k):
			if s[i] not in d:
				d[s[i]] = 1
			else:
				d[s[i]] += 1
		if len(d) == k - 1:
			c += 1
		j = 0
		for i in range(k, len(s)):
			d[s[j]] -= 1
			if d[s[j]] == 0:
				d.pop(s[j])
			if s[i] not in d:
				d[s[i]] = 1
			else:
				d[s[i]] += 1
			if len(d) == k - 1:
				c += 1
			j += 1
		return c


from collections import defaultdict

class Solution:

	def countOfSubstrings(self, s, k):
		ans = 0
		distinct = 0
		cnt = defaultdict(int)
		for i in range(k):
			cnt[s[i]] += 1
			if cnt[s[i]] == 1:
				distinct += 1
		if distinct == k - 1:
			ans += 1
		for j in range(k, len(s)):
			i = j - k
			cnt[s[j]] += 1
			if cnt[s[j]] == 1:
				distinct += 1
			cnt[s[i]] -= 1
			if cnt[s[i]] == 0:
				distinct -= 1
			if distinct == k - 1:
				ans += 1
		return ans


class Solution:

	def countOfSubstrings(self, s, k):
		i = j = 0
		count = 0
		mapper = dict()
		n = len(s)
		while j < n:
			mapper[s[j]] = 1 + mapper.get(s[j], 0)
			if j - i + 1 == k:
				if len(mapper) == k - 1:
					count += 1
				if mapper[s[i]] - 1 == 0:
					mapper.pop(s[i])
				else:
					mapper[s[i]] -= 1
				i += 1
			j += 1
		return count


from collections import deque

class Solution:

	def countOfSubstrings(self, s, k):
		q = deque()
		ans = 0
		d = {}
		count = 0
		for i in range(k):
			q.append(s[i])
			if s[i] not in d or d[s[i]] == 0:
				d[s[i]] = 1
				count += 1
			else:
				d[s[i]] += 1
		for i in range(k, len(s)):
			if count == k - 1:
				ans += 1
			x = q.popleft()
			d[x] -= 1
			if d[x] == 0:
				count -= 1
			q.append(s[i])
			if s[i] not in d or d[s[i]] == 0:
				d[s[i]] = 1
				count += 1
			else:
				d[s[i]] += 1
		if count == k - 1:
			ans += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		ans = 0
		hash = {}
		for i in range(K):
			hash[S[i]] = hash.get(S[i], 0) + 1
		if len(hash) == K - 1:
			ans += 1
		for i in range(K, len(S)):
			hash[S[i]] = hash.get(S[i], 0) + 1
			hash[S[i - K]] -= 1
			if hash[S[i - K]] == 0:
				del hash[S[i - K]]
			if len(hash) == K - 1:
				ans += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		d = {}
		(i, j) = (0, 0)
		n = len(S)
		ans = 0
		while j < n:
			if S[j] not in d:
				d[S[j]] = 1
			else:
				d[S[j]] += 1
			if j - i + 1 < K:
				j += 1
			elif j - i + 1 == K:
				if len(d) == K - 1:
					ans += 1
				d[S[i]] -= 1
				if d[S[i]] == 0:
					del d[S[i]]
				i += 1
				j += 1
		return ans


class Solution:

	def countOfSubstrings(self, s, k):
		if k - 1 == 0:
			return 0
		dic = {}
		i = 0
		ct = 0
		for j in range(len(s)):
			dic[s[j]] = 1 + dic.get(s[j], 0)
			if len(dic) == k - 1 and j - i + 1 == k:
				ct += 1
				dic[s[i]] -= 1
				if dic[s[i]] == 0:
					dic.pop(s[i])
				i += 1
			while j - i + 1 == k:
				dic[s[i]] -= 1
				if dic[s[i]] == 0:
					dic.pop(s[i])
				i += 1
		return ct


from collections import defaultdict
import collections

class Solution:

	def countOfSubstrings(self, S, K):
		if not S:
			return
		n = len(S)
		if K > n:
			return 0
		res = 0
		mp = collections.defaultdict(int)
		for i in range(K):
			mp[S[i]] += 1
		if len(mp) == K - 1:
			res += 1
		r = K
		while r < n:
			mp[S[r - K]] -= 1
			if mp[S[r - K]] == 0:
				del mp[S[r - K]]
			mp[S[r]] += 1
			if len(mp) == K - 1:
				res += 1
			r += 1
		return res


from collections import defaultdict

class Solution:

	def countOfSubstrings(self, S, K):
		d = defaultdict(lambda : 0)
		c = 0
		ans = 0
		for i in range(K):
			if d[S[i]] == 0:
				c += 1
			d[S[i]] += 1
		if c == K - 1:
			ans += 1
		for i in range(K, len(S)):
			d[S[i - K]] -= 1
			if d[S[i - K]] == 0:
				c -= 1
			if d[S[i]] == 0:
				c += 1
			d[S[i]] += 1
			if c == K - 1:
				ans += 1
		return ans


class Solution:

	def countOfSubstrings(self, s, k):
		count = 0
		mp = {}
		for i in range(k):
			if s[i] not in mp:
				mp[s[i]] = 1
			else:
				mp[s[i]] += 1
		if len(mp) == k - 1:
			count += 1
		j = 0
		n = len(s)
		for i in range(k, n):
			a = s[i]
			b = s[j]
			if b in mp:
				mp[b] -= 1
				if mp[b] == 0:
					del mp[b]
			if a not in mp:
				mp[a] = 1
			else:
				mp[a] += 1
			j += 1
			if len(mp) == k - 1:
				count += 1
		return count


class Solution:

	def countOfSubstrings(self, s, K):
		n = len(s)
		d = {}
		c = 0
		r = 0
		for i in range(K):
			if s[i] not in d:
				d[s[i]] = 1
				c += 1
			else:
				d[s[i]] += 1
		if c == K - 1:
			r += 1
		for i in range(K, n):
			d[s[i - K]] -= 1
			if d[s[i - K]] == 0:
				c -= 1
				d.pop(s[i - K])
			if s[i] not in d:
				d[s[i]] = 1
				c += 1
			else:
				d[s[i]] += 1
			if c == K - 1:
				r += 1
		return r


class Solution:

	def countOfSubstrings(self, S, k):
		n = len(S)
		count = 0
		freq = {}
		start = end = 0
		while end < n:
			ch = S[end]
			freq[ch] = freq.get(ch, 0) + 1
			if end - start + 1 > k:
				ch = S[start]
				freq[ch] -= 1
				start += 1
				if freq[ch] == 0:
					freq.pop(ch)
			if end - start + 1 == k and len(freq) == k - 1:
				count += 1
			end += 1
		return count


class Solution:

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


class Solution:

	def countOfSubstrings(self, S, K):
		ma = {}
		coun = 0
		for k in range(K):
			if S[k] in ma:
				ma[S[k]] += 1
			else:
				ma[S[k]] = 1
		ans = 0
		if len(ma) == K - 1:
			ans = ans + 1
		i = K
		j = 0
		while i <= len(S) - 1:
			i = i + 1
			j = j + 1
			t_r = S[j - 1]
			t_a = S[i - 1]
			ma[t_r] -= 1
			if ma[t_r] == 0:
				del ma[t_r]
			if t_a not in ma:
				ma[t_a] = 1
			else:
				ma[t_a] += 1
			if len(ma) == K - 1:
				ans += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		ans = 0
		cnt = 0
		di = dict()
		for i in range(K):
			di[S[i]] = di.get(S[i], 0) + 1
			if di[S[i]] == 1:
				cnt += 1
		if cnt == K - 1:
			ans += 1
		for i in range(K, len(S)):
			di[S[i - K]] -= 1
			if di[S[i - K]] == 0:
				cnt -= 1
			di[S[i]] = di.get(S[i], 0) + 1
			if di[S[i]] == 1:
				cnt += 1
			if cnt == K - 1:
				ans += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		if K == 1:
			return 0
		small = {}
		big = {}
		i = 0
		j = 0
		idx = 0
		res = 0
		while idx < len(S):
			while i < len(S) and (not (len(small) == K - 2 and S[i] not in small)):
				if S[i] not in small:
					small[S[i]] = 1
				else:
					small[S[i]] += 1
				i += 1
			while j < len(S) and (not (len(big) == K - 1 and S[j] not in big)):
				if S[j] not in big:
					big[S[j]] = 1
				else:
					big[S[j]] += 1
				j += 1
			if K - 2 == 0:
				i = idx
			if i - idx < K and j - 1 - idx >= K - 1:
				res += 1
			if S[idx] in small:
				small[S[idx]] -= 1
				if small[S[idx]] == 0:
					small.pop(S[idx])
			if S[idx] in big:
				big[S[idx]] -= 1
				if big[S[idx]] == 0:
					big.pop(S[idx])
			idx += 1
		return res


from collections import Counter

class Solution:

	def countOfSubstrings(self, S, K):
		freq_window = Counter(S[:K])
		K_count = 1 if len(freq_window) == K - 1 else 0
		n = len(S)
		for i in range(K, n):
			freq_window[S[i]] += 1
			freq_window[S[i - K]] -= 1
			if freq_window[S[i - K]] <= 0:
				del freq_window[S[i - K]]
			if len(freq_window) == K - 1:
				K_count += 1
		return K_count


class Solution:

	def countOfSubstrings(self, strr, k):
		N = len(strr)
		answer = 0
		mapp = {}
		for i in range(K):
			try:
				mapp[strr[i]] += 1
			except:
				mapp[strr[i]] = 1
		if len(mapp) == K - 1:
			answer += 1
		for i in range(K, N):
			try:
				mapp[strr[i]] += 1
			except:
				mapp[strr[i]] = 1
			mapp[strr[i - K]] -= 1
			if mapp[strr[i - K]] == 0:
				del mapp[strr[i - K]]
			if len(mapp) == K - 1:
				answer += 1
		return answer


class Solution:

	def countOfSubstrings(self, str, k):
		N = len(str)
		answer = 0
		map = {}
		for i in range(K):
			try:
				map[str[i]] += 1
			except:
				map[str[i]] = 1
		if len(map) == K - 1:
			answer += 1
		for i in range(K, N):
			try:
				map[str[i]] += 1
			except:
				map[str[i]] = 1
			map[str[i - K]] -= 1
			if map[str[i - K]] == 0:
				del map[str[i - K]]
			if len(map) == K - 1:
				answer += 1
		return answer


class Solution:

	def countOfSubstrings(self, s, k):
		arr = [0 for i in range(26)]
		i = 0
		j = 0
		n = len(s)
		c = 0
		count = 0
		while j < n:
			arr[ord(s[j]) - 97] += 1
			if arr[ord(s[j]) - 97] == 1:
				c += 1
			if j - i + 1 == k:
				if c == k - 1:
					count += 1
				arr[ord(s[i]) - 97] -= 1
				if arr[ord(s[i]) - 97] == 0:
					c -= 1
				i += 1
			j += 1
		return count


class Solution:

	def countOfSubstrings(self, S, k):
		s = {}
		count = 0
		for i in range(len(S)):
			if S[i] in s.keys():
				s[S[i]] += 1
			else:
				s[S[i]] = 1
			if i == k - 1:
				if len(s) == k - 1:
					count += 1
			if i >= k:
				s[S[i - k]] -= 1
				if s[S[i - k]] == 0:
					s.pop(S[i - k])
				if len(s) == k - 1:
					count += 1
		return count


class Solution:

	def countOfSubstrings(self, S, K):
		char_freq = [0] * 26
		(l, res, distinct) = (0, 0, 0)
		for i in range(len(S)):
			indx = ord(S[i]) - ord('a')
			char_freq[indx] += 1
			if char_freq[indx] == 1:
				distinct += 1
			if i >= K:
				char_freq[ord(S[l]) - ord('a')] -= 1
				if not char_freq[ord(S[l]) - ord('a')]:
					distinct -= 1
				l += 1
			if i >= K - 1 and distinct == K - 1:
				res += 1
		return res


class Solution:

	def countOfSubstrings(self, S, K):
		start = 0
		end = 0
		map = {}
		count = 0
		ans = 0
		while end < len(S):
			if S[end] not in map or not map[S[end]]:
				count += 1
				map[S[end]] = 1
			else:
				map[S[end]] += 1
			if end - start + 1 < K:
				end += 1
			elif end - start + 1 == K:
				if count == K - 1:
					ans += 1
				map[S[start]] -= 1
				if not map[S[start]]:
					count -= 1
				start += 1
				end += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		d = dict()
		for i in range(K):
			d[S[i]] = d.get(S[i], 0) + 1
		r = len(d)
		c = 0
		if r == K - 1:
			c += 1
		j = 0
		for i in range(K, len(S)):
			d[S[i]] = d.get(S[i], 0) + 1
			d[S[j]] = d.get(S[j], 0) - 1
			if d.get(S[j]) == 0:
				d.pop(S[j])
			if len(d) == K - 1:
				c += 1
			j += 1
		return c


class Solution:

	def countOfSubstrings(self, S, K):
		(ans, dist, n) = (0, 0, len(S))
		fre = [0] * 26
		for i in range(K):
			fre[ord(S[i]) - 97] += 1
			if fre[ord(S[i]) - 97] == 1:
				dist += 1
		if dist == K - 1:
			ans += 1
		for i in range(K, n):
			fre[ord(S[i - K]) - 97] -= 1
			if fre[ord(S[i - K]) - 97] == 0:
				dist -= 1
			fre[ord(S[i]) - 97] += 1
			if fre[ord(S[i]) - 97] == 1:
				dist += 1
			if dist == K - 1:
				ans += 1
		return ans


class Solution:

	def countOfSubstrings(self, s, k):
		from collections import defaultdict
		d = defaultdict(int)
		count = 0
		for i in range(k):
			d[s[i]] += 1
		if len(d) == k - 1:
			count += 1
		for i in range(k, len(s)):
			d[s[i]] += 1
			d[s[i - k]] -= 1
			if d[s[i - k]] == 0:
				del d[s[i - k]]
			if len(d) == k - 1:
				count += 1
		return count


class Solution:

	def countOfSubstrings(self, S, k):
		n = len(S)
		cnt = 0
		hm = {}
		for i in range(0, k):
			hm[S[i]] = 1 + hm.get(S[i], 0)
		if len(hm) == k - 1:
			cnt += 1
		i = 0
		for j in range(k, n):
			prev = S[i]
			hm[prev] -= 1
			if hm[prev] == 0:
				del hm[prev]
			i += 1
			new = S[j]
			hm[new] = 1 + hm.get(new, 0)
			if len(hm) == k - 1:
				cnt += 1
		return cnt


class Solution:

	def countOfSubstrings(self, S, K):
		i = 0
		j = 0
		dic = {}
		cnt = 0
		rs = 0
		while j <= len(S):
			if j - i == K:
				if len(dic) == K - 1:
					rs += 1
				if S[i] in dic:
					if dic[S[i]] == 1:
						del dic[S[i]]
						cnt -= 1
					elif dic[S[i]] == 2:
						dic[S[i]] -= 1
						cnt += 1
					else:
						dic[S[i]] -= 1
					i += 1
			elif j - i < K and j < len(S):
				if S[j] in dic:
					dic[S[j]] += 1
					if dic[S[j]] == 2:
						cnt -= 1
				else:
					dic[S[j]] = 1
					cnt += 1
				j += 1
			else:
				break
		return rs


class Solution:

	def countOfSubstrings(self, S, K):
		cnt = 0
		d = {}
		for i in range(K):
			if S[i] not in d:
				d[S[i]] = 1
			else:
				d[S[i]] += 1
		if len(d) == K - 1:
			cnt += 1
		for j in range(K, len(S)):
			if d[S[j - K]] == 1:
				del d[S[j - K]]
			else:
				d[S[j - K]] -= 1
			if S[j] not in d:
				d[S[j]] = 1
			else:
				d[S[j]] += 1
			if len(d) == K - 1:
				cnt += 1
		return cnt


class Solution:

	def countOfSubstrings(self, S, K):
		x = 0
		s = {}
		for i in range(K):
			if s.get(S[i]):
				s[S[i]] += 1
			else:
				s[S[i]] = 1
		(i, j) = (0, K)
		while j <= len(S):
			if len(s) == K - 1:
				x += 1
			if j != len(S):
				if s[S[i]] == 1:
					s.pop(S[i])
				else:
					s[S[i]] -= 1
				if s.get(S[j]):
					s[S[j]] += 1
				else:
					s[S[j]] = 1
			(i, j) = (i + 1, j + 1)
		return x


class Solution:

	def countOfSubstrings(self, s, k):
		i = j = 0
		n = len(s)
		tmp = ''
		res = 0
		mp = {}
		while j < n:
			if mp.__contains__(s[j]):
				mp[s[j]] += 1
			else:
				mp[s[j]] = 1
			if j - i + 1 == k:
				if len(mp) == k - 1:
					res += 1
				mp[s[i]] -= 1
				if mp[s[i]] == 0:
					mp.pop(s[i])
				i += 1
			j += 1
		return res


class Solution:

	def countOfSubstrings(self, S, K):
		if len(S) < K:
			return 0
		d = {}
		uniq = 0
		ans = 0
		for i in range(K):
			if S[i] in d:
				d[S[i]] += 1
			else:
				uniq += 1
				d[S[i]] = 1
		if uniq == K - 1:
			ans += 1
		r = K
		while r < len(S):
			d[S[r - K]] -= 1
			if d[S[r - K]] == 0:
				uniq -= 1
				del d[S[r - K]]
			if S[r] in d:
				d[S[r]] += 1
			else:
				uniq += 1
				d[S[r]] = 1
			if uniq == K - 1:
				ans += 1
			r += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		if K > 27:
			return 0
		result = 0
		for i in range(len(S) - K + 1):
			A = S[i:i + K]
			if len(set(A)) == K - 1:
				result += 1
		return result


class Solution:

	def countOfSubstrings(self, S, K):
		if K > 27:
			return 0
		count = 0
		subs = ''
		for i in range(len(S) - K + 1):
			if i:
				subs = subs + S[i + K - 1]
				subs = subs[1:]
			else:
				subs = S[0:K]
			if len(set(subs)) + 1 == K:
				count += 1
		return count


class Solution:

	def countOfSubstrings(self, s, k):
		(i, j) = (0, 0)

		def check(d, k):
			count = 0
			fl = 0
			for i in d:
				if d[i] != 0:
					if d[i] > 2:
						return False
					elif d[i] == 2:
						if fl == 1:
							return False
						else:
							fl = 1
					count += 1
			if count == k - 1:
				return True
		output = 0
		d = {}
		while j < len(s):
			if j - i + 1 < k:
				if s[j] in d:
					d[s[j]] += 1
				else:
					d[s[j]] = 1
				j += 1
			elif j - i + 1 == k:
				if s[j] in d:
					d[s[j]] += 1
				else:
					d[s[j]] = 1
				if check(d, k):
					output += 1
				d[s[i]] -= 1
				j += 1
				i += 1
		return output


class Solution:

	def countOfSubstrings(self, S, K):
		fr = [0] * 26
		d = 0
		c = 0
		for i in range(K):
			fr[ord(S[i]) - 97] += 1
			if fr[ord(S[i]) - 97] == 1:
				d += 1
		if d == K - 1:
			c += 1
		le = 0
		ri = K
		while ri < len(S):
			fr[ord(S[le]) - 97] -= 1
			if fr[ord(S[le]) - 97] == 0:
				d -= 1
			fr[ord(S[ri]) - 97] += 1
			if fr[ord(S[ri]) - 97] == 1:
				d += 1
			if d == K - 1:
				c += 1
			le += 1
			ri += 1
		return c


class Solution:

	def countOfSubstrings(self, s, k):
		d = {}
		ans = 0
		n = len(s)
		j = 0
		for i in range(k):
			d[s[i]] = i
		if len(d) == k - 1:
			ans += 1
		for i in range(k, n):
			if d[s[j]] == j:
				del d[s[j]]
			j += 1
			d[s[i]] = i
			if len(d) == k - 1:
				ans += 1
		return ans


from collections import deque

class Solution:

	def countOfSubstrings(self, S, K):
		s = deque(S)
		sq = deque()
		dsm = {}
		ct = 0
		while len(s) > 0:
			ele = s.popleft()
			sq.append(ele)
			if ele in dsm:
				dsm[ele] = dsm[ele] + 1
			else:
				dsm[ele] = 1
			ct = ct + 1
			if ct == K:
				break
		rslt = 0
		if len(dsm.keys()) == K - 1:
			rslt = rslt + 1
		while len(s) > 0:
			ele = s.popleft()
			sq.append(ele)
			che = sq.popleft()
			if dsm[che] > 1:
				dsm[che] = dsm[che] - 1
			else:
				dsm.pop(che)
			if ele in dsm:
				dsm[ele] = dsm[ele] + 1
			else:
				dsm[ele] = 1
			if len(dsm.keys()) == K - 1:
				rslt = rslt + 1
		return rslt


class Solution:

	def countOfSubstrings(self, S, K):
		n = len(S)
		dp = [0 for i in range(26)]
		solve = 0
		con = 0
		for i in range(0, n):
			c = ord(S[i]) - ord('a')
			if dp[c] == 0:
				con += 1
			dp[c] += 1
			if i >= K:
				dp[ord(S[i - K]) - ord('a')] -= 1
				if dp[ord(S[i - K]) - ord('a')] == 0:
					con -= 1
			if i >= K - 1 and con == K - 1:
				solve += 1
		return solve


class Solution:

	def countOfSubstrings(self, s, k):
		count = {}
		ctr = 0
		ans = 0
		for i in range(k):
			if not count.get(s[i], 0):
				ctr += 1
			count[s[i]] = 1 + count.get(s[i], 0)
		if ctr == k - 1:
			ans += 1
		for i in range(k, len(s)):
			if count[s[i - k]] == 1:
				ctr -= 1
			count[s[i - k]] -= 1
			if not count.get(s[i], 0):
				ctr += 1
			count[s[i]] = 1 + count.get(s[i], 0)
			if ctr == k - 1:
				ans += 1
		return ans


class Solution:

	def fun(self, K, S):
		n = len(S)
		count = 0
		for i in range(0, n - K + 1):
			j = i
			s = ''
			while j < K + i:
				s = s + S[j]
				j += 1
			if len(set(s)) == K - 1:
				count += 1
		return count

	def fun2(self, S, K):
		ma = {}
		coun = 0
		for k in range(K):
			if S[k] in ma:
				ma[S[k]] += 1
			else:
				ma[S[k]] = 1
		ans = 0
		if len(ma) == K - 1:
			ans = ans + 1
		i = K
		j = 0
		while i <= len(S) - 1:
			i = i + 1
			j = j + 1
			t_r = S[j - 1]
			t_a = S[i - 1]
			ma[t_r] -= 1
			if ma[t_r] == 0:
				del ma[t_r]
			if t_a not in ma:
				ma[t_a] = 1
			else:
				ma[t_a] += 1
			if len(ma) == K - 1:
				ans += 1
		return ans

	def countOfSubstrings(self, S, K):
		return self.fun2(S, K)


from collections import defaultdict

class Solution:

	def countOfSubstrings(self, S, K):
		n = len(S)
		res = 0
		hMap = defaultdict(int)
		for i in range(K):
			hMap[S[i]] += 1
		if len(hMap) == K - 1:
			res += 1
		for i in range(K, n):
			hMap[S[i - K]] -= 1
			if hMap[S[i - K]] == 0:
				del hMap[S[i - K]]
			hMap[S[i]] += 1
			if len(hMap) == K - 1:
				res += 1
		return res


class Solution:

	def countOfSubstrings(self, S, K):
		from collections import OrderedDict
		y = {}
		ans = 0
		for i in range(K):
			y[S[i]] = y.get(S[i], 0) + 1
		if len(y) == K - 1:
			ans += 1
		for i in range(K, len(S)):
			y[S[i]] = y.get(S[i], 0) + 1
			if y[S[i - K]] == 1:
				y.pop(S[i - K])
			else:
				y[S[i - K]] -= 1
			if len(y) == K - 1:
				ans += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		res = 0
		(i, j) = (0, 0)
		map = {}
		while i < len(S):
			map[S[i]] = 1 + map.get(S[i], 0)
			if i + 1 >= K:
				if len(map) == K - 1:
					res = res + 1
				map[S[j]] -= 1
				if map[S[j]] == 0:
					del map[S[j]]
				j = j + 1
			i = i + 1
		return res


class Solution:

	def countOfSubstrings(self, S, K):
		N = len(S)
		answer = 0
		map = {}
		for i in range(K):
			map[S[i]] = map.get(S[i], 0) + 1
		if len(map) == K - 1:
			answer += 1
		for i in range(K, N):
			map[S[i]] = map.get(S[i], 0) + 1
			map[S[i - K]] -= 1
			if map[S[i - K]] == 0:
				del map[S[i - K]]
			if len(map) == K - 1:
				answer += 1
		return answer


class Solution:

	def countOfSubstrings(self, S, K):
		result = 0
		uniq_chars = {}
		for i in range(K):
			if S[i] not in uniq_chars:
				uniq_chars[S[i]] = 0
			uniq_chars[S[i]] += 1
		uniq_count = 0
		for (k, v) in uniq_chars.items():
			if v > 0:
				uniq_count += 1
		if uniq_count == K - 1:
			result += 1
		ibeg = 0
		iend = K
		while iend < len(S):
			uniq_chars[S[ibeg]] -= 1
			if S[iend] not in uniq_chars:
				uniq_chars[S[iend]] = 0
			uniq_chars[S[iend]] += 1
			uniq_count = 0
			for (k, v) in uniq_chars.items():
				if v > 0:
					uniq_count += 1
			if uniq_count == K - 1:
				result += 1
			ibeg += 1
			iend += 1
		return result


from collections import Counter

class Solution:

	def countOfSubstrings(self, S, k):
		n = len(S)
		window = Counter(S[:k])
		distinct = len(window)
		count = 1 if distinct == k - 1 else 0
		for end in range(k, n):
			if window[S[end - k]] == 1:
				distinct -= 1
			window[S[end - k]] -= 1
			window[S[end]] += 1
			if window[S[end]] == 1:
				distinct += 1
			if distinct == k - 1:
				count += 1
		return count


class Solution:

	def countOfSubstrings(self, S, K):
		import numpy as np
from collections import defaultdict

class Solution:

	def countOfSubstrings(self, s, K):
		(start, end) = (0, 0)
		n = len(s)
		d = {}
		ans = 0
		while end < n:
			if s[end] not in d:
				d[s[end]] = 1
			else:
				d[s[end]] += 1
			if end - start + 1 == K:
				if len(d) == K - 1:
					ans += 1
				d[s[start]] -= 1
				if d[s[start]] == 0:
					d.pop(s[start])
				start += 1
			end += 1
		return ans


import numpy as np

class Solution:

	def countOfSubstrings(self, S, K):
		(res, diff, n) = (0, 0, len(S))
		new = [0] * 26
		for i in range(K):
			new[ord(S[i]) - 97] += 1
			if new[ord(S[i]) - 97] == 1:
				diff += 1
		if diff == K - 1:
			res += 1
		for i in range(K, n):
			new[ord(S[i - K]) - 97] -= 1
			if new[ord(S[i - K]) - 97] == 0:
				diff -= 1
			new[ord(S[i]) - 97] += 1
			if new[ord(S[i]) - 97] == 1:
				diff += 1
			if diff == K - 1:
				res += 1
		return res


class Solution:

	def countOfSubstrings(self, S, K):
		if K == 1:
			return 0
		dic = {}
		n = len(S)
		ans = 0
		for i in range(K):
			dic.setdefault(S[i], 0)
			dic[S[i]] += 1
		cnt = len(dic.keys())
		if cnt == K - 1:
			ans += 1
		for i in range(K, n):
			dic[S[i - K]] -= 1
			if dic[S[i - K]] == 0:
				cnt -= 1
			if S[i] in dic.keys() and dic[S[i]] != 0:
				dic[S[i]] += 1
			else:
				dic[S[i]] = 1
				cnt += 1
			if cnt == K - 1:
				ans += 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		d = dict()
		ct = 0
		for i in range(K):
			d[S[i]] = d.get(S[i], 0) + 1
		if len(d) == K - 1:
			ct += 1
		for i in range(K, len(S)):
			d[S[i - K]] -= 1
			if not d[S[i - K]]:
				d.pop(S[i - K])
			d[S[i]] = d.get(S[i], 0) + 1
			if len(d) == K - 1:
				ct += 1
		return ct


class Solution:

	def countOfSubstrings(self, S, K):
		cons = 0
		current_chars = {}
		for i in range(K):
			if current_chars.get(S[i], 0) == 0:
				current_chars[S[i]] = 1
			else:
				current_chars[S[i]] += 1
		if len(current_chars) == K - 1:
			cons += 1
		for i in range(K, len(S)):
			first_char = S[i - K]
			if current_chars[first_char] <= 1:
				del current_chars[first_char]
			else:
				current_chars[first_char] -= 1
			current_chars[S[i]] = current_chars.get(S[i], 0) + 1
			if len(current_chars) == K - 1:
				cons += 1
		return cons


class Solution:

	def countOfSubstrings(self, S, K):
		d = dict()
		dist = 0
		for i in range(K):
			j = S[i]
			if j in d.keys():
				d[j] = d.get(j) + 1
			else:
				dist += 1
				d[j] = 1
		tot = 0
		if dist == K - 1:
			tot += 1
		top_ind = 0
		for i in S[K:]:
			top = S[top_ind]
			if d[top] == 1:
				del d[top]
				dist -= 1
			else:
				d[top] = d.get(top) - 1
			if i in d.keys():
				d[i] = d.get(i) + 1
			else:
				dist += 1
				d[i] = 1
			if dist == K - 1:
				tot += 1
			top_ind += 1
		return tot


class Solution:

	def countOfSubstrings(self, s, k):
		i = 0
		j = 0
		dic = {}
		count = 0
		while j < len(s):
			if s[j] in dic.keys():
				t = dic.get(s[j])
				dic[s[j]] = t + 1
			else:
				dic[s[j]] = 1
			if j - i + 1 < k:
				j = j + 1
			elif j - i + 1 == k:
				if len(dic) == k - 1:
					count = count + 1
				if dic.get(s[i]) == 1:
					del dic[s[i]]
				else:
					u = dic.get(s[i])
					dic[s[i]] = u - 1
				i = i + 1
				j = j + 1
		return count


import collections

class Solution:

	def countOfSubstrings(self, s, k):
		d = collections.defaultdict(int)
		count = 0
		ans = 0
		for i in range(k - 1):
			if d[s[i]] == 0:
				d[s[i]] = 1
				count += 1
			else:
				d[s[i]] += 1
		for i in range(k - 1, len(s)):
			if d[s[i]] == 0:
				d[s[i]] = 1
				count += 1
			else:
				d[s[i]] += 1
			if count == k - 1:
				ans += 1
			d[s[i - k + 1]] -= 1
			if d[s[i - k + 1]] == 0:
				count -= 1
		return ans


class Solution:

	def countOfSubstrings(self, S, K):
		hm = {}
		final_answer = 0
		for i in range(K):
			if S[i] in hm:
				hm[S[i]] += 1
			else:
				hm[S[i]] = 1
		if len(hm) == K - 1:
			final_answer += 1
		i = 0
		j = K
		while j < len(S):
			hm[S[i]] -= 1
			if hm[S[i]] == 0:
				del hm[S[i]]
			if S[j] in hm:
				hm[S[j]] += 1
			else:
				hm[S[j]] = 1
			if len(hm) == K - 1:
				final_answer += 1
			j += 1
			i += 1
		return final_answer


class Solution:

	def countOfSubstrings(self, S, K):
		res = list()
		l = 0
		n = len(S)
		count = 0
		map = dict()
		for r in range(n):
			map[S[r]] = map.get(S[r], 0) + 1
			if r - l + 1 == K:
				if len(map) == K - 1:
					count += 1
				if map.get(S[l], 0) > 1:
					map[S[l]] = map.get(S[l]) - 1
				else:
					del map[S[l]]
				l += 1
		return count