Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that have exactly k distinct characters. 
Example 1:
Input:
S = "aba", K = 2
Output:
3
Explanation:
The substrings are:
"ab", "ba" and "aba".
Example 2:
Input: 
S = "abaaca", K = 1
Output:
7
Explanation:
The substrings are:
"a", "b", "a", "aa", "a", "c", "a". 
Your Task:
You don't need to read input or print anything. Your task is to complete the function substrCount() which takes the string S and an integer K as inputs and returns the number of substrings having exactly K distinct characters.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ |S| ≤ 10^{5}
1 ≤ K ≤ 26

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def substrCount (self,s, k):

        # your code here

Solutions:
from collections import defaultdict, deque

class Solution:

	def substrCount(self, s, k):

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


from collections import defaultdict

class Solution:

	def most_k_chars(self, s, k):
		if not s:
			return 0
		char_count = {}
		num = 0
		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
			num += i - left + 1
		return num

	def substrCount(self, s, k):
		return self.most_k_chars(s, k) - self.most_k_chars(s, k - 1)


class Solution:

	def substrCount(self, s, k):

		def atmost_k(s, k):
			freq = {}
			cnt = 0
			j = 0
			for i in range(len(s)):
				freq[s[i]] = freq.get(s[i], 0) + 1
				while len(freq) > k:
					freq[s[j]] -= 1
					if freq[s[j]] == 0:
						freq.pop(s[j])
					j += 1
				cnt += i - j + 1
			return cnt
		return atmost_k(s, k) - atmost_k(s, k - 1)


class Solution:

	def substrCount(self, s, k):
		st = {x: 0 for x in 'abcdefghijklmnopqrstuvwxyz'}
		i = 0
		c = 0
		c1 = 0
		for j in range(len(s)):
			st[s[j]] += 1
			if st[s[j]] == 1:
				c += 1
			while c > k:
				st[s[i]] -= 1
				if st[s[i]] == 0:
					c -= 1
				i += 1
			c1 += j - i + 1
		st = {x: 0 for x in 'abcdefghijklmnopqrstuvwxyz'}
		k -= 1
		i = 0
		c = 0
		c2 = 0
		for j in range(len(s)):
			st[s[j]] += 1
			if st[s[j]] == 1:
				c += 1
			while c > k:
				st[s[i]] -= 1
				if st[s[i]] == 0:
					c -= 1
				i += 1
			c2 += j - i + 1
		return c1 - c2


def solve(s, k):
	count = 0
	d = dict()
	start = 0
	for i in range(len(s)):
		if s[i] in d:
			d[s[i]] += 1
		else:
			d[s[i]] = 1
		while len(d) > k:
			d[s[start]] -= 1
			if d[s[start]] == 0:
				del d[s[start]]
			start += 1
		count += i - start + 1
	return count

class Solution:

	def substrCount(self, s, k):
		return solve(s, k) - solve(s, k - 1)


import collections

class Solution:

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

	def geni(self, s, K):
		(n, count, left, right) = (len(s), 0, 0, 0)
		mp = collections.defaultdict(int)
		while right < n:
			mp[s[right]] += 1
			while len(mp) > K:
				mp[s[left]] -= 1
				if mp[s[left]] == 0:
					del mp[s[left]]
				left += 1
			count += right - left + 1
			right += 1
		return count

	def substrCount(self, s, k):
		return self.gen(s, k) - self.gen(s, k - 1)


class Solution:

	def substrCount(self, s, k):
		(last, ts) = ([-1] * 26, [])
		ans = 0
		for (i, c) in enumerate(s):
			v = ord(c) - 97
			if last[v] >= 0:
				ts.remove(last[v])
			last[v] = i
			ts.append(i)
			M = len(ts)
			if M > k:
				ans += ts[-k] - ts[-k - 1]
			elif M == k:
				ans += ts[0] + 1
		return ans


class Solution:

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

	def substrCount(self, s, k):
		return self.atmostk(s, k) - self.atmostk(s, k - 1)


class Solution:

	def substrCount(self, s, k):

		def util(s, k):
			if not s:
				return 0
			mapp = {}
			num = 0
			left = 0
			for i in range(len(s)):
				mapp[s[i]] = mapp.get(s[i], 0) + 1
				while len(mapp) > k:
					mapp[s[left]] -= 1
					if mapp[s[left]] == 0:
						del mapp[s[left]]
					left += 1
				num += i - left + 1
			return num
		result = util(s, k) - util(s, k - 1)
		return result


class Solution:

	def helper(self, s, k):
		mp = {}
		ans = 0
		startWindow = 0
		for endWindow in range(len(s)):
			if s[endWindow] 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 += endWindow - startWindow + 1
		return ans

	def substrCount(self, s, k):
		return self.helper(s, k) - self.helper(s, k - 1)


class Solution:

	def substrCount(self, s, k):
		from collections import Counter

		def f(q):
			c = Counter([])
			n = len(s)
			st = 0
			res = 0
			for i in range(n):
				c[s[i]] += 1
				while len(c) > q:
					c[s[st]] -= 1
					if c[s[st]] == 0:
						del c[s[st]]
					st += 1
				res += i - st + 1
			return res
		return f(k) - f(k - 1)


from collections import defaultdict

class Solution:

	def substrCount(self, s, k):
		ans = self.helper(s, k) - self.helper(s, k - 1)
		return ans

	def helper(self, s, k):
		left = 0
		n = len(s)
		hmap = defaultdict(int)
		ans = 0
		for right in range(0, n):
			if s[right] not in hmap:
				hmap[s[right]] = 1
			else:
				hmap[s[right]] += 1
			while left <= right and len(hmap) > k:
				hmap[s[left]] -= 1
				if hmap[s[left]] == 0:
					del hmap[s[left]]
				left += 1
			ans += right - left + 1
		return ans


class Solution:

	def substrCount(self, s, k):
		return self.atmostK(s, k) - self.atmostK(s, k - 1)

	def atmostK(self, s, k):
		count = 0
		i = 0
		j = 0
		dit = dict()
		while j < len(s):
			if s[j] in dit:
				dit[s[j]] += 1
			else:
				dit[s[j]] = 1
			while len(dit) > k:
				dit[s[i]] -= 1
				if dit[s[i]] == 0:
					del dit[s[i]]
				i += 1
			count += j - i + 1
			j += 1
		return count


class Solution:

	def substrCount(self, str1, k):

		def most_k_chars(s, k):
			if not s:
				return 0
			char_count = {}
			num = 0
			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
				num += i - left + 1
			return num
		return most_k_chars(s, k) - most_k_chars(s, k - 1)


def find(s, k):
	c = 0
	d = {}
	si = 0
	dcc = 0
	n = len(s)
	for i in range(n):
		if s[i] in d:
			d[s[i]] += 1
		else:
			d[s[i]] = 1
			dcc += 1
		while dcc > k:
			d[s[si]] -= 1
			if d[s[si]] == 0:
				dcc -= 1
				del d[s[si]]
			si += 1
		c += i - si + 1
	return c

class Solution:

	def substrCount(self, s, k):
		c1 = find(s, k)
		c2 = find(s, k - 1)
		return c1 - c2


class Solution:

	def substrCount(self, s, k):
		ans = self.solve(s, k) - self.solve(s, k - 1)
		return ans

	def solve(self, s, k):
		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:
				dict1[s[j]] -= 1
				if dict1[s[j]] == 0:
					del dict1[s[j]]
				j += 1
			count += i - j + 1
		return count


from collections import defaultdict

class Solution:

	def substrCount(self, s, k):
		return self.solve(s, k) - self.solve(s, k - 1)

	def solve(self, s, k):
		low = 0
		check = defaultdict(int)
		count = 0
		for high in range(len(s)):
			check[s[high]] += 1
			while len(check) > k:
				check[s[low]] -= 1
				if check[s[low]] == 0:
					del check[s[low]]
				low += 1
			count += high - low + 1
		return count


class Solution:

	def substrCount(self, s, k):
		return self.most_k_char(s, k) - self.most_k_char(s, k - 1)

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


from collections import defaultdict

class Solution:

	def substrCount(self, s, k):
		s = list(s)
		count = 0
		(right, left) = (0, 0)
		hmap = defaultdict(int)
		for x in s:
			hmap[x] += 1
			if len(hmap) < k:
				continue
			if len(hmap) > k:
				del hmap[s[right]]
				right += 1
				left = right
			while hmap[s[right]] > 1:
				hmap[s[right]] -= 1
				right += 1
			count += right - left + 1
		return count


class Solution:

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

	def substrCount(self, s, k):
		return self.solve(s, k) - self.solve(s, k - 1)


class Solution:

	def substrCount(self, s, k):
		result = self.at_most_character(s, k) - self.at_most_character(s, k - 1)
		return result

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


class Solution:

	def substrCount(self, s, k):

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


class Solution:

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

	def substrCount(self, s, k):
		return self.countChars(s, k) - self.countChars(s, k - 1)


class Solution:

	def substrCount(self, s, k):
		return self.counts(s, k) - self.counts(s, k - 1)

	def counts(self, s, k):
		m = dict()
		count = 0
		i = 0
		j = 0
		while j < len(s):
			if s[j] in m:
				m[s[j]] += 1
			else:
				m[s[j]] = 1
			while i <= j and len(m) > k:
				m[s[i]] -= 1
				if m[s[i]] == 0:
					del m[s[i]]
				i += 1
			count += j - i + 1
			j += 1
		return count


from collections import Counter

class Solution:

	def atmost(self, s, k):
		freq = dict()
		total = 0
		start = 0
		for i in range(len(s)):
			freq[s[i]] = freq.get(s[i], 0) + 1
			while len(freq) > k:
				freq[s[start]] -= 1
				if freq[s[start]] == 0:
					freq.pop(s[start])
				start += 1
			total += i - start + 1
		return total

	def substrCount(self, s, k):
		return self.atmost(s, k) - self.atmost(s, k - 1)


from collections import defaultdict

class Solution:

	def substrCount(self, s, k):
		c = defaultdict(lambda : 0)
		count = 0
		n = len(s)
		i = 0
		j = 0
		for item in s:
			while i < n and len(c) < k:
				c[s[i]] += 1
				i += 1
			while j < n and s[j] in c:
				j += 1
			if len(c) == k:
				count += j - i + 1
			c[item] -= 1
			if c[item] == 0:
				del c[item]
		return count


class Solution:

	def substrCount(self, s, k):

		def lek(s, k):
			(i, j) = (0, 0)
			res = 0
			dictionary = dict()
			while j < len(s):
				if s[j] in dictionary:
					dictionary[s[j]] += 1
				else:
					dictionary[s[j]] = 1
				c = len(dictionary)
				if c < k:
					res += j - i + 1
					j += 1
				elif c == k:
					res += j - i + 1
					j += 1
				elif c > k:
					while c > k:
						dictionary[s[i]] -= 1
						if dictionary[s[i]] == 0:
							del dictionary[s[i]]
							c -= 1
						i += 1
					res += j - i + 1
					j += 1
			return res
		return lek(s, k) - lek(s, k - 1)


from collections import defaultdict

class Solution:

	def substrCount(self, s, k):

		def lek(s, k):
			(i, j) = (0, 0)
			res = 0
			dictionary = defaultdict(int)
			while j < len(s):
				if s[j] in dictionary:
					dictionary[s[j]] += 1
				else:
					dictionary[s[j]] = 1
				c = len(dictionary)
				if c > k:
					while c > k:
						dictionary[s[i]] -= 1
						if dictionary[s[i]] == 0:
							del dictionary[s[i]]
							c -= 1
						i += 1
				res += j - i + 1
				j += 1
			return res
		return lek(s, k) - lek(s, k - 1)


class Solution:

	def substrCount(self, s, k):

		def fun(k):
			d = {}
			start = 0
			m = 0
			f = 0
			for end in range(len(s)):
				d[s[end]] = 1 + d.get(s[end], 0)
				f = 0
				while len(d) > k:
					d[s[start]] -= 1
					if d[s[start]] == 0:
						del d[s[start]]
					start += 1
				m += end - start + 1
			return m
		return fun(k) - fun(k - 1)


class Solution:

	def solve(self, s, k):
		i = 0
		j = 0
		dis_cou = 0
		hash_arr = [0] * 26
		ans = 0
		while j < len(s):
			if hash_arr[ord(s[j]) - ord('a')] == 0:
				dis_cou += 1
			hash_arr[ord(s[j]) - ord('a')] += 1
			while dis_cou > k:
				hash_arr[ord(s[i]) - ord('a')] -= 1
				if hash_arr[ord(s[i]) - ord('a')] == 0:
					dis_cou -= 1
				i += 1
			ans += j - i + 1
			j += 1
		return ans

	def substrCount(self, s, k):
		ans = self.solve(s, k) - self.solve(s, k - 1)
		return ans


import collections

class Solution:

	def substrCount(self, S, K):
		s = list(S)

		def atMost(k):
			count = collections.defaultdict(int)
			left = 0
			ans = 0
			for (right, x) in enumerate(s):
				count[x] += 1
				while len(count) > k:
					count[s[left]] -= 1
					if count[s[left]] == 0:
						del count[s[left]]
					left += 1
				ans += right - left + 1
			return ans
		return atMost(K) - atMost(K - 1)


class Solution:

	def substrCount(self, s, k):
		length = len(s)
		ans = 0
		ib = -1
		ism = -1
		mapB = {}
		mapS = {}
		j = -1
		if k == 1:
			ans = 0
			lastChar = s[0]
			lastIndex = 0
			for i in range(len(s)):
				curChar = s[i]
				if lastChar == curChar:
					ans += i - lastIndex + 1
				else:
					ans += 1
					lastIndex = i
					lastChar = curChar
			return ans

		def removeFromMap(char, charmap):
			if charmap[char] == 1:
				charmap.pop(char)
				return
			charmap[char] -= 1
		while True:
			f1 = False
			f2 = False
			f3 = False
			while ib < length - 1:
				f1 = True
				ib += 1
				char = s[ib]
				mapB[char] = mapB.get(char, 0) + 1
				if len(mapB) == k + 1:
					ib -= 1
					removeFromMap(char, mapB)
					break
			while ism < length - 1:
				f2 = True
				ism += 1
				char = s[ism]
				mapS[char] = mapS.get(char, 0) + 1
				if len(mapS) == k:
					ism -= 1
					removeFromMap(char, mapS)
					break
			while j < ism:
				f3 = True
				j += 1
				char = s[j]
				if len(mapS) == k - 1 and len(mapB) == k:
					ans += ib - ism
				removeFromMap(char, mapB)
				removeFromMap(char, mapS)
				if len(mapS) != k - 1 or len(mapB) != k:
					break
			if not f1 and (not f2) and (not f3):
				break
		return ans


class Solution:

	def substrCount(self, s, k):

		def solve(st, k):
			mp = dict()
			s = set()
			l = 0
			ans = 0
			for r in range(len(st)):
				if st[r] not in mp.keys():
					mp[st[r]] = 1
				else:
					mp[st[r]] += 1
				s.add(st[r])
				while len(s) > k:
					mp[st[l]] -= 1
					if mp[st[l]] == 0:
						s.remove(st[l])
					l += 1
				ans += r - l + 1
			return ans
		return solve(s, k) - solve(s, k - 1)


def atmost(s, k):
	n = len(s)
	if n == 0:
		return 0
	d = {}
	x = 0
	y = 0
	for i in range(n):
		if s[i] not in d:
			d[s[i]] = 1
		else:
			d[s[i]] += 1
		while len(d) > k:
			d[s[y]] -= 1
			if d[s[y]] == 0:
				d.pop(s[y])
			y += 1
		x += i - y + 1
	return x

class Solution:

	def substrCount(self, s, k):
		return atmost(s, k) - atmost(s, k - 1)


from collections import deque, Counter, defaultdict as dd

class Solution:

	def substrCount(self, s, k):

		def func(s, k):
			d = dd(int)
			n = len(s)
			i = 0
			j = 0
			ans = 0
			while j < n:
				d[s[j]] += 1
				while len(d) > k:
					if d[s[i]] <= 1:
						d.pop(s[i])
					else:
						d[s[i]] -= 1
					i += 1
				ans += j - i + 1
				j += 1
			return ans
		a = func(s, k)
		b = func(s, k - 1)
		return a - b


class Solution:

	def most_k_char(self, s, k):
		(num, left) = (0, 0)
		hash = {}
		if len(s) == 0:
			return 0
		for i in range(len(s)):
			hash[s[i]] = hash.get(s[i], 0) + 1
			while len(hash) > k:
				hash[s[left]] -= 1
				if hash[s[left]] == 0:
					del hash[s[left]]
				left += 1
			num += i - left + 1
		return num

	def substrCount(self, s, k):
		return self.most_k_char(s, k) - self.most_k_char(s, k - 1)


class Solution:

	def substrCount(self, s, k):
		(ans, st, dp) = (0, 0, {})
		last = 0
		for e in range(len(s)):
			dp[s[e]] = dp.get(s[e], 0) + 1
			if len(dp) > k:
				(ei, n) = (st, {})
				while len(dp) > k:
					n[s[ei]] = n.get(s[ei], 0) + 1
					while len(n) == k:
						ans += e - ei
						n[s[st]] -= 1
						dp[s[st]] -= 1
						if not n[s[st]]:
							del n[s[st]]
						if not dp[s[st]]:
							del dp[s[st]]
						st += 1
					ei += 1
		if len(dp) == k:
			if len(dp) == k:
				(n, e) = ({}, st)
				while e < len(s):
					n[s[e]] = n.get(s[e], 0) + 1
					while len(n) == k:
						ans += len(s) - e
						n[s[st]] -= 1
						if not n[s[st]]:
							del n[s[st]]
						st += 1
					e += 1
		return ans


class Solution:

	def substrCount(self, string, k):

		def findsubs(maxK):
			n = len(string)
			normal = {}
			dist_cnt = 0
			subs = 0
			(s, e) = (0, 0)
			while e < n:
				normal[string[e]] = 1 + normal.get(string[e], 0)
				if normal[string[e]] == 1:
					dist_cnt += 1
				while dist_cnt > maxK:
					normal[string[s]] -= 1
					if normal[string[s]] == 0:
						dist_cnt -= 1
					s += 1
				subs += e - s + 1
				e += 1
			return subs
		a = findsubs(k)
		b = findsubs(k - 1)
		return a - b


class Solution:

	def solve(self, s, k):
		ans = 0
		(i, j) = (-1, -1)
		h = {}
		while True:
			while i < len(s) - 1:
				i += 1
				h[s[i]] = h.get(s[i], 0) + 1
				if len(h) <= k:
					ans += i - j
				else:
					break
			if i == len(s) - 1 and len(h) <= k:
				break
			while j < i:
				j += 1
				if h[s[j]] == 1:
					del h[s[j]]
				else:
					h[s[j]] -= 1
				if len(h) > k:
					continue
				else:
					ans += i - j
					break
		return ans

	def substrCount(self, s, k):
		return self.solve(s, k) - self.solve(s, k - 1)


class Solution:

	def substrCount(self, s, k):
		return self.getAtmost(s, k) - self.getAtmost(s, k - 1)

	def getAtmost(self, s, k):
		freqMap = {}
		right = left = 0
		countSubString = 0
		while right < len(s):
			freqMap[s[right]] = freqMap.get(s[right], 0) + 1
			while len(freqMap) > k:
				freqMap[s[left]] -= 1
				if freqMap[s[left]] == 0:
					freqMap.pop(s[left])
				left += 1
			countSubString += right - left + 1
			right += 1
		return countSubString


from collections import defaultdict

def count(s, k):
	c = 0
	dic = defaultdict(lambda : 0)
	start = 0
	ans = 0
	for i in range(len(s)):
		if dic[s[i]] == 0:
			c += 1
		dic[s[i]] += 1
		while c > k and start < len(s):
			dic[s[start]] -= 1
			if dic[s[start]] == 0:
				c -= 1
			start += 1
		ans += i - start + 1
	return ans

class Solution:

	def substrCount(self, s, k):
		return count(s, k) - count(s, k - 1)


class Solution:

	def exact_k_chars(self, s, k):
		memo = {}
		Count = 0
		left = 0
		for i in range(len(s)):
			if s[i] in memo:
				memo[s[i]] += 1
			else:
				memo[s[i]] = 1
			while len(memo) > k:
				memo[s[left]] -= 1
				if memo[s[left]] == 0:
					del memo[s[left]]
				left += 1
			Count += i - left + 1
		return Count

	def substrCount(self, s, k):
		return self.exact_k_chars(s, k) - self.exact_k_chars(s, k - 1)


from collections import Counter

class Solution:

	def atMostK(self, A, K):
		count = Counter()
		res = i = 0
		for j in range(len(A)):
			if count[A[j]] == 0:
				K -= 1
			count[A[j]] += 1
			while K < 0:
				count[A[i]] -= 1
				if count[A[i]] == 0:
					K += 1
				i += 1
			res += j - i + 1
		return res

	def substrCount(self, A, K):
		return self.atMostK(A, K) - self.atMostK(A, K - 1)


from collections import defaultdict

class Solution:

	def substrCount(self, s, k):
		return self.helper_func(s, k) - self.helper_func(s, k - 1)

	def helper_func(self, s, k):
		count = defaultdict(int)
		(left, res) = (0, 0)
		for right in range(len(s)):
			count[s[right]] += 1
			while len(count) > k:
				count[s[left]] -= 1
				if count[s[left]] == 0:
					del count[s[left]]
				left += 1
			res += right - left + 1
		return res


class Solution:

	def countAtMostK(self, s, k):
		start = end = ans = 0
		mp = {}
		while end < len(s):
			if s[end] in mp.keys():
				mp[s[end]] += 1
			else:
				mp[s[end]] = 1
			while len(mp) > k:
				mp[s[start]] -= 1
				if mp[s[start]] == 0:
					mp.pop(s[start])
				start += 1
			ans += end - start + 1
			end += 1
		return ans

	def substrCount(self, s, k):
		return self.countAtMostK(s, k) - self.countAtMostK(s, k - 1)


class Solution:

	def substrCount(self, s, k):
		return self.solve(s, k) - self.solve(s, k - 1)

	def solve(self, s, k):
		ans = distCnt = release = 0
		mp = {}
		for aquire in range(len(s)):
			currChar = s[aquire]
			if currChar in mp:
				mp[currChar] += 1
			else:
				distCnt += 1
				mp[currChar] = 1
			while release <= aquire and distCnt > k:
				discardChar = s[release]
				mp[discardChar] -= 1
				release += 1
				if mp[discardChar] == 0:
					del mp[discardChar]
					distCnt -= 1
			ans += aquire - release + 1
		return ans


class Solution:

	def substrCount(self, s, k):
		n = len(s)
		if k > n:
			return 0
		i = 0
		j = 1
		d = {s[0]: 1}
		di = {s[0]: 0}
		r = 1
		res = 0
		if k == 1:
			res = 1
		while i <= j and j < n:
			if s[j] not in di:
				if r < k:
					di[s[j]] = j
					r += 1
				else:
					mini = j
					for x in di:
						if mini > di[x]:
							mini = di[x]
						if di[x] == mini:
							p = x
					del di[p]
					di[s[j]] = j
					i = mini + 1
			else:
				di[s[j]] = j
			if r == k:
				mini = j
				for x in di:
					if mini > di[x]:
						mini = di[x]
				res += mini - i + 1
			j += 1
		return res


class Solution:

	def at_most_k(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
			while len(freq) > k:
				ch = s[start]
				freq[ch] -= 1
				if freq[ch] == 0:
					freq.pop(ch)
				start += 1
			count += end - start + 1
			end += 1
		return count

	def substrCount(self, s, k):
		return self.at_most_k(s, k) - self.at_most_k(s, k - 1)


from collections import defaultdict

class Solution:

	def atMostK(self, s, k):
		if k < 0:
			return 0
		i = 0
		j = 0
		cnt = 0
		res = 0
		m = [0 for i in range(26)]
		while j < len(s):
			m[ord(s[j]) - ord('a')] += 1
			if m[ord(s[j]) - ord('a')] == 1:
				cnt += 1
			while cnt > k:
				m[ord(s[i]) - ord('a')] -= 1
				if m[ord(s[i]) - ord('a')] == 0:
					cnt -= 1
				i += 1
			res += j - i + 1
			j += 1
		return res

	def substrCount(self, s, k):
		return self.atMostK(s, k) - self.atMostK(s, k - 1)


class Solution:

	def solve(self, s, k):
		d = {}
		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
			while len(d) > k:
				d[s[i]] -= 1
				if d[s[i]] == 0:
					d.pop(s[i])
				i += 1
			count += j - i + 1
			j += 1
		return count

	def substrCount(self, s, k):
		return self.solve(s, k) - self.solve(s, k - 1)


class Solution:

	def substrCount(self, s, k):
		smallhash = {}
		biggerhash = {}
		idx = 0
		i = 0
		j = 0
		res = 0
		while idx < len(s):
			while i < len(s) and (not (len(smallhash) == k - 1 and s[i] not in smallhash)):
				if s[i] not in smallhash:
					smallhash[s[i]] = 1
				else:
					smallhash[s[i]] += 1
				i += 1
			while j < len(s) and (not (len(biggerhash) == k and s[j] not in biggerhash)):
				if s[j] not in biggerhash:
					biggerhash[s[j]] = 1
				else:
					biggerhash[s[j]] += 1
				j += 1
			if i >= len(s) or len(smallhash) != k - 1:
				break
			if j >= len(s) and len(biggerhash) != k:
				break
			if i < idx:
				i = idx
			res += j - i
			if s[idx] in smallhash:
				smallhash[s[idx]] -= 1
				if smallhash[s[idx]] == 0:
					smallhash.pop(s[idx])
			if s[idx] in biggerhash:
				biggerhash[s[idx]] -= 1
				if biggerhash[s[idx]] == 0:
					biggerhash.pop(s[idx])
			idx += 1
		return res


def f(A, k):
	n = len(A)
	i = 0
	j = 0
	freq = [0] * 26
	d = 0
	ans = 0
	while j < n:
		o = ord(A[j]) - ord('a')
		freq[o] += 1
		if freq[o] == 1:
			d += 1
		while d > k:
			o = ord(A[i]) - ord('a')
			freq[o] -= 1
			if freq[o] == 0:
				d -= 1
			i += 1
		ans += j - i + 1
		j += 1
	return ans

class Solution:

	def substrCount(self, S, k):
		return f(S, k) - f(S, k - 1)


class Solution:

	def substrCount(self, s, k):

		def countStrings(diff):
			if diff == 0:
				return 0
			left = 0
			right = 0
			count = 0
			dicti = {}
			while right < len(s):
				if s[right] in dicti:
					dicti[s[right]] += 1
				else:
					dicti[s[right]] = 1
				while len(dicti) > diff:
					dicti[s[left]] -= 1
					if dicti[s[left]] == 0:
						dicti.pop(s[left])
					left += 1
				count += right - left + 1
				right += 1
			return count
		return countStrings(k) - countStrings(k - 1)


class Solution:

	def substrCount(self, s, k):
		return solve(s, k) - solve(s, k - 1)

def solve(s, k):
	count = 0
	hash = {}
	left = 0
	for right in range(len(s)):
		hash[s[right]] = 1 + hash.get(s[right], 0)
		while len(hash) > k:
			hash[s[left]] -= 1
			if hash[s[left]] == 0:
				hash.pop(s[left])
			left += 1
		count += right - left + 1
	return count


class Solution:

	def count(self, s, n, k):
		m = {}
		j = 0
		c = 0
		for i in range(n):
			if s[i] in m:
				m[s[i]] += 1
			else:
				m[s[i]] = 1
			while len(m) > k:
				m[s[j]] -= 1
				if m[s[j]] == 0:
					del m[s[j]]
				j += 1
			c += i - j
		return c

	def substrCount(self, s, k):
		n = len(s)
		return self.count(s, n, k) - self.count(s, n, k - 1)


class Solution:

	def substrCount(self, s, k):
		if k == 1:
			n = len(s)
			c = 1
			f = 0
			for i in range(n - 1):
				if s[i] == s[i + 1]:
					c += 1
				else:
					f += c * (c + 1) // 2
					c = 1
			f += c * (c + 1) // 2
			return f
		m1 = {}
		m2 = {}
		ism = -1
		ib = -1
		j = -1
		c = 0
		n = len(s)
		while True:
			f1 = 0
			f2 = 0
			f3 = 0
			while ib < n - 1:
				f1 = 1
				ib += 1
				if s[ib] in m1:
					m1[s[ib]] += 1
				else:
					m1[s[ib]] = 1
				if len(m1) == k + 1:
					del m1[s[ib]]
					ib -= 1
					break
			while ism < n - 1:
				f2 = 1
				ism += 1
				if s[ism] in m2:
					m2[s[ism]] += 1
				else:
					m2[s[ism]] = 1
				if len(m2) == k:
					del m2[s[ism]]
					ism -= 1
					break
			while j < ism:
				f3 = 1
				if len(m1) == k and len(m2) == k - 1:
					c += ib - ism
				j += 1
				g = s[j]
				m1[g] -= 1
				if m1[g] == 0:
					del m1[g]
				m2[g] -= 1
				if m2[g] == 0:
					del m2[g]
				if len(m1) < k or len(m2) < k - 1:
					break
			if f1 == 0 and f2 == 0 and (f3 == 0):
				break
		return c