Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.
(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)
Return the number of good subarrays of A.
 
Example 1:
Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:
Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

 
Note:

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Mathematics

Starter code: class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        

Solutions:
from collections import defaultdict

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		start_k = 0
		start = 0
		elem_dict = defaultdict(int)
		ans = 0
		for elem in A:
			elem_dict[elem] += 1
			if len(elem_dict) > K:
				del elem_dict[A[start_k]]
				start_k += 1
				start = start_k
			if len(elem_dict) == K:
				while elem_dict[A[start_k]] > 1:
					elem_dict[A[start_k]] -= 1
					start_k += 1
				ans = ans + start_k - start + 1
		return ans


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		if K > len(A):
			return 0
		result = checker = windowStart = 0
		hashMap = {}
		a_length = len(A)
		for windowEnd in range(a_length):
			curr_str = A[windowEnd]
			if curr_str in hashMap:
				hashMap[curr_str] += 1
			else:
				hashMap[curr_str] = 1
			if len(hashMap) > K:
				del hashMap[A[checker]]
				checker += 1
				windowStart = checker
			if len(hashMap) == K:
				while hashMap[A[checker]] > 1:
					hashMap[A[checker]] -= 1
					checker += 1
				result += checker - windowStart + 1
		return result


from collections import OrderedDict

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		counter = OrderedDict()
		count = 0
		j = 0
		for (i, n) in enumerate(A):
			counter[n] = i
			counter.move_to_end(n)
			while len(counter) > K:
				j = counter.popitem(last=False)[1] + 1
			if len(counter) == K:
				count += next(iter(counter.values())) - j + 1
		return count


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		(ans, ctr, lb, count) = (0, {}, 0, 0)
		for (i, val) in enumerate(A):
			if val not in ctr:
				ctr[val] = 0
			ctr[val] += 1
			while len(ctr) > K:
				ctr[A[lb]] -= 1
				if ctr[A[lb]] == 0:
					del ctr[A[lb]]
				lb += 1
			if len(ctr) == K:
				(p2, count, ctr1) = (lb, 0, collections.Counter())
				while len(ctr) == K:
					count += 1
					ctr[A[p2]] -= 1
					if ctr[A[p2]] == 0:
						del ctr[A[p2]]
					ctr1[A[p2]] += 1
					p2 += 1
				ans += count
				for (k, v) in ctr1.items():
					ctr[k] = ctr.get(k, 0) + v
		return ans

class Window:

	def __init__(self):
		self.count = collections.Counter()
		self.nonzero = 0

	def add(self, x):
		self.count[x] += 1
		if self.count[x] == 1:
			self.nonzero += 1

	def remove(self, x):
		self.count[x] -= 1
		if self.count[x] == 0:
			self.nonzero -= 1

class Solution(object):

	def subarraysWithKDistinct(self, A, K):
		window1 = Window()
		window2 = Window()
		ans = left1 = left2 = 0
		for (right, x) in enumerate(A):
			window1.add(x)
			window2.add(x)
			while window1.nonzero > K:
				window1.remove(A[left1])
				left1 += 1
			while window2.nonzero >= K:
				window2.remove(A[left2])
				left2 += 1
			ans += left2 - left1
		return ans


class Window:

	def __init__(self):
		self.count = collections.Counter()
		self.nonzero = 0

	def add(self, x):
		self.count[x] += 1
		if self.count[x] == 1:
			self.nonzero += 1

	def remove(self, x):
		self.count[x] -= 1
		if self.count[x] == 0:
			self.nonzero -= 1

class Solution(object):

	def subarraysWithKDistinct(self, A, K):
		window1 = Window()
		window2 = Window()
		ans = left1 = left2 = 0
		for (right, x) in enumerate(A):
			window1.add(x)
			window2.add(x)
			while window1.nonzero > K:
				window1.remove(A[left1])
				left1 += 1
			while window2.nonzero >= K:
				window2.remove(A[left2])
				left2 += 1
			ans += left2 - left1
		return ans


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		from collections import Counter

		def atMost(k):
			count = Counter()
			ans = i = 0
			for j in range(len(A)):
				if not count[A[j]]:
					k -= 1
				count[A[j]] += 1
				while k < 0:
					count[A[i]] -= 1
					if not count[A[i]]:
						k += 1
					i += 1
				ans += j - i + 1
			return ans
		return atMost(K) - atMost(K - 1)


from collections import defaultdict

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		one = self.atMostK(A, K)
		two = self.atMostK(A, K - 1)
		print((one, two))
		return one - two

	def atMostK(self, nums, k):
		mapping = defaultdict(int)
		ans = 0
		left = 0
		for right in range(len(nums)):
			mapping[nums[right]] += 1
			if mapping[nums[right]] == 1:
				k -= 1
			while k < 0:
				mapping[nums[left]] -= 1
				if mapping[nums[left]] == 0:
					k += 1
				left += 1
			ans += right - left + 1
		return ans


class Solution:
	from collections import Counter

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

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


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		start = 0
		first_uni = 0
		re = 0
		dd = {}
		for (i, cur) in enumerate(A):
			dd[cur] = dd.get(cur, 0) + 1
			if len(dd) == K + 1:
				dd.pop(A[first_uni])
				first_uni += 1
				start = first_uni
			if len(dd) == K:
				while first_uni <= i and dd[A[first_uni]] != 1:
					dd[A[first_uni]] -= 1
					first_uni += 1
				re += first_uni - start + 1
		return re


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		N = len(A)

		def atMost(k):
			if k == 0:
				return 0
			ret = i = j = 0
			cnt = Counter()
			while i < N:
				x = A[i]
				while j < N and (len(cnt) < k or A[j] in cnt):
					cnt[A[j]] += 1
					j += 1
				ret += j - i
				cnt[x] -= 1
				if cnt[x] == 0:
					del cnt[x]
				i += 1
			return ret
		return atMost(K) - atMost(K - 1)


class Solution:

	def subarraysWithKDistinct(self, s: List[int], K: int) -> int:
		obj = defaultdict(int)
		first = 0
		second = 0
		answer = 0
		for i in range(len(s)):
			obj[s[i]] += 1
			if len(obj) == K + 1:
				del obj[s[second]]
				second += 1
				first = second
			if len(obj) == K:
				while obj[s[second]] > 1:
					obj[s[second]] -= 1
					second += 1
				answer += second - first + 1
		return answer


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		length = len(A)

		class counter:

			def __init__(self):
				self.c = Counter()

			def addValue(self, num):
				self.c[num] += 1

			def removeValue(self, num):
				self.c[num] -= 1
				if self.c[num] == 0:
					del self.c[num]

		def subarraysWithAtLeast(k):
			start = 0
			c = counter()
			ret = 0
			for i in range(length):
				cur = A[i]
				c.addValue(cur)
				if len(c.c) < k:
					ret += i - start + 1
					continue
				while len(c.c) > k:
					tmp = A[start]
					c.removeValue(tmp)
					start += 1
				assert len(c.c) == k
				ret += i - start + 1
			return ret
		return subarraysWithAtLeast(K) - subarraysWithAtLeast(K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		int_dict = {}
		int_sorted_list = []
		current = 0
		l = len(A)
		count = 0
		while current < l:
			if int_dict.get(A[current]) != None:
				int_sorted_list.remove(A[current])
			int_dict[A[current]] = current
			int_sorted_list.append(A[current])
			if len(int_sorted_list) > K + 1:
				del int_dict[int_sorted_list[0]]
				del int_sorted_list[0]
			if len(int_sorted_list) > K:
				count += int_dict[int_sorted_list[-K]] - int_dict[int_sorted_list[-K - 1]]
			elif len(int_sorted_list) == K:
				count += int_dict[int_sorted_list[-K]] + 1
			current += 1
		return count


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atmostK(k):
			count = Counter()
			res = 0
			left = 0
			right = 0
			for right in range(len(A)):
				if count[A[right]] == 0:
					k -= 1
				count[A[right]] += 1
				while k < 0:
					count[A[left]] -= 1
					if count[A[left]] == 0:
						k += 1
					left += 1
				res += right - left + 1
			return res
		return atmostK(K) - atmostK(K - 1)


class Window:

	def __init__(self):
		self.count = {}

	def add(self, elem):
		self.count.setdefault(elem, 0)
		self.count[elem] += 1

	def remove(self, elem):
		self.count[elem] -= 1
		if self.count[elem] == 0:
			del self.count[elem]

	def added_size(self, elem):
		return len(self.count) + bool(elem not in self.count)

def count_below(arr, k):
	if k == 0:
		return 0
	else:
		right = 0
		satisfactory = 0
		window = Window()
		for left in range(len(arr)):
			while right < len(arr) and window.added_size(arr[right]) <= k:
				window.add(arr[right])
				right += 1
			satisfactory += right - left
			window.remove(arr[left])
		return satisfactory

def subarrays_with_k_distinct(arr, k):
	assert k >= 1
	return count_below(arr, k) - count_below(arr, k - 1)

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return subarrays_with_k_distinct(A, K)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		result = 0
		(i, j) = (0, 0)
		cnt = collections.Counter()
		l = 0
		n = len(A)
		while j < n:
			if len(cnt) != K:
				cnt[A[j]] += 1
				if len(cnt) == K:
					l = 1
					while cnt[A[i]] > 1:
						cnt[A[i]] -= 1
						i += 1
						l += 1
					result += l
			elif A[j] in cnt:
				cnt[A[j]] += 1
				while cnt[A[i]] > 1:
					cnt[A[i]] -= 1
					i += 1
					l += 1
				result += l
			else:
				cnt[A[i]] -= 1
				if cnt[A[i]] == 0:
					cnt.pop(A[i])
				cnt[A[j]] += 1
				i += 1
				l = 1
				while cnt[A[i]] > 1:
					cnt[A[i]] -= 1
					i += 1
					l += 1
				result += l
			j += 1
		return result


class Window:

	def __init__(self):
		self.counter = collections.Counter()

	def add(self, x):
		self.counter[x] += 1

	def remove(self, x):
		self.counter[x] -= 1
		if self.counter[x] == 0:
			self.counter.pop(x)

	def __len__(self):
		return len(self.counter)

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		window1 = Window()
		window2 = Window()
		(left1, left2) = (0, 0)
		result = 0
		for (right, num) in enumerate(A):
			window1.add(num)
			window2.add(num)
			while len(window1) > K:
				window1.remove(A[left1])
				left1 += 1
			while len(window2) >= K:
				window2.remove(A[left2])
				left2 += 1
			result += left2 - left1
		return result


class Accumulator:

	def __init__(self):
		self.KeyToCount = {}
		self.q = deque()

	def append(self, value):
		self.q.append(value)
		self.KeyToCount[value] = self.KeyToCount.get(value, 0) + 1

	def popleft(self):
		v = self.q.popleft()
		if self.KeyToCount[v] == 1:
			del self.KeyToCount[v]
		else:
			self.KeyToCount[v] -= 1

	def distinctCount(self):
		return len(self.KeyToCount)

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		n = len(A)
		nextHiIdx = 0
		nextLoIdx = 0
		loAcc = Accumulator()
		hiAcc = Accumulator()
		lo = [None] * n
		hi = [None] * n
		for i in range(n):
			if i >= 1:
				hiAcc.popleft()
				loAcc.popleft()
			while nextLoIdx < n and loAcc.distinctCount() < K:
				loAcc.append(A[nextLoIdx])
				nextLoIdx += 1
			while nextHiIdx < n and hiAcc.distinctCount() <= K:
				hiAcc.append(A[nextHiIdx])
				nextHiIdx += 1
			if loAcc.distinctCount() == K:
				lo[i] = nextLoIdx - 1
			if hiAcc.distinctCount() == K + 1:
				hi[i] = nextHiIdx - 1
			elif hiAcc.distinctCount() == K and nextHiIdx == n:
				hi[i] = nextHiIdx
		return sum((hi[i] - lo[i] for i in range(n) if hi[i] != None))


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMost(K):
			N = len(A)
			ct = collections.Counter()
			ans = 0
			i = 0
			for j in range(N):
				ct[A[j]] += 1
				if len(ct) <= K:
					ans += j - i + 1
				else:
					while len(ct) > K:
						ct[A[i]] -= 1
						if ct[A[i]] == 0:
							del ct[A[i]]
						i += 1
					ans += j - i + 1
			return ans
		return atMost(K) - atMost(K - 1)


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		window1 = Window()
		window2 = Window()
		res = 0
		(left1, left2) = (0, 0)
		for i in range(len(A)):
			window1.add(A[i])
			window2.add(A[i])
			while window1.size() > K:
				window1.remove(A[left1])
				left1 += 1
			while window2.size() > K - 1:
				window2.remove(A[left2])
				left2 += 1
			res += left2 - left1
		return res

class Window:

	def __init__(self):
		self.counter = Counter()

	def add(self, x):
		self.counter[x] += 1

	def remove(self, x):
		self.counter[x] -= 1
		if self.counter[x] == 0:
			del self.counter[x]

	def size(self):
		return len(self.counter)


class Solution:

	def subarraysWithKDistinct(self, A: 'List[int]', K: 'int') -> 'int':
		return self.subarraysWithKMax(A, K) - self.subarraysWithKMax(A, K - 1)

	def subarraysWithKMax(self, A, K):
		k = 0
		count = dict()
		(i, start) = (0, 0)
		res = 0
		while i < len(A):
			if A[i] not in count:
				k += 1
				count[A[i]] = 1
			else:
				count[A[i]] += 1
			i += 1
			while start < i and k > K:
				count[A[start]] -= 1
				if count[A[start]] == 0:
					del count[A[start]]
					k -= 1
				start += 1
			res += i - start
		return res


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.atMostK(A, K) - self.atMostK(A, K - 1)

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


from collections import Counter

class Window:

	def __init__(self):
		self.count = Counter()
		self.nonzero = 0

	def add(self, val):
		self.count[val] += 1
		if self.count[val] == 1:
			self.nonzero += 1

	def remove(self, val):
		self.count[val] -= 1
		if self.count[val] == 0:
			self.nonzero -= 1

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		ans = 0
		(l1, l2) = (0, 0)
		(w1, w2) = (Window(), Window())
		for (r, val) in enumerate(A):
			w1.add(val)
			w2.add(val)
			while w1.nonzero > K:
				w1.remove(A[l1])
				l1 += 1
			while w2.nonzero >= K:
				w2.remove(A[l2])
				l2 += 1
			ans += l2 - l1
		return ans


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		class UniqueCounter(object):

			def __init__(self):
				self.non_zero = 0
				self.counts = collections.defaultdict(int)

			def add(self, x):
				if self.counts[x] == 0:
					self.non_zero += 1
				self.counts[x] += 1

			def remove(self, x):
				self.counts[x] -= 1
				if self.counts[x] == 0:
					self.non_zero -= 1

			def count(self):
				return self.non_zero

		def subarrays_with_max_K(A, K):
			j = 0
			uc = UniqueCounter()
			uc.add(A[0])
			answer = 0
			for i in range(len(A)):
				while j < len(A) and uc.count() <= K:
					j += 1
					if j < len(A):
						uc.add(A[j])
				answer += j - i
				uc.remove(A[i])
			return answer
		return subarrays_with_max_K(A, K) - subarrays_with_max_K(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		last_seen = {}
		start = end = 0
		ans = 0
		for (i, x) in enumerate(A):
			last_seen[x] = i
			while len(last_seen) > K:
				if last_seen[A[start]] == start:
					del last_seen[A[start]]
				start += 1
			while A[end] not in last_seen or last_seen[A[end]] != end:
				end += 1
			if len(last_seen) == K:
				ans += end - start + 1
		return ans


from collections import Counter

def solve(A, K):
	count = Counter()
	front = iter(A)
	ans = 0
	size = 0
	for k in A:
		count[k] += 1
		size += 1
		while len(count) > K:
			key = next(front)
			count[key] -= 1
			size -= 1
			if count[key] == 0:
				del count[key]
		ans += size
	return ans

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return solve(A, K) - solve(A, K - 1)


class Window:

	def __init__(self):
		self.count = collections.Counter()
		self.nonzero = 0

	def add(self, x):
		self.count[x] += 1
		if self.count[x] == 1:
			self.nonzero += 1

	def remove(self, x):
		self.count[x] -= 1
		if self.count[x] == 0:
			self.nonzero -= 1

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		window1 = Window()
		window2 = Window()
		ans = le1 = le2 = 0
		for (ri, val) in enumerate(A):
			window1.add(val)
			window2.add(val)
			while window1.nonzero > K:
				window1.remove(A[le1])
				le1 += 1
			while window2.nonzero >= K:
				window2.remove(A[le2])
				le2 += 1
			ans += le2 - le1
		return ans


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		n = len(A)
		if n < 1:
			return 0
		result = 0
		fc = Counter()
		c = Counter()
		l = 0
		fr = 0
		r = 0
		while l < n:
			while fr < n and len(fc) < K:
				fc[A[fr]] += 1
				fr += 1
			while r < n:
				if A[r] not in c and len(c) >= K:
					break
				c[A[r]] += 1
				r += 1
			if len(c) == K:
				result += r - fr + 1
			fc[A[l]] -= 1
			if fc[A[l]] == 0:
				del fc[A[l]]
			c[A[l]] -= 1
			if c[A[l]] == 0:
				del c[A[l]]
			l += 1
			print('c', l, r)
		return result


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.at_most(A, K) - self.at_most(A, K - 1)

	def at_most(self, a, k):
		res = 0
		start = 0
		c = Counter()
		for (end, elem) in enumerate(a):
			if c[elem] == 0:
				k -= 1
			c[elem] += 1
			while start <= end and k < 0:
				c[a[start]] -= 1
				if c[a[start]] == 0:
					k += 1
				start += 1
			res += end - start + 1
		return res


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMostK(A, K):
			counts = Counter()
			(left, result) = (0, 0)
			for right in range(len(A)):
				if counts[A[right]] == 0:
					K -= 1
				counts[A[right]] += 1
				while K < 0:
					counts[A[left]] -= 1
					if counts[A[left]] == 0:
						K += 1
					left += 1
				result += right - left + 1
			return result
		return atMostK(A, K) - atMostK(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		if not A:
			return 0
		l = len(A)
		end = 0
		left1 = 0
		left2 = 0
		map1 = collections.defaultdict(int)
		map2 = collections.defaultdict(int)
		ans = 0
		while end < l:
			ch = A[end]
			map1[ch] += 1
			map2[ch] += 1
			while len(map1) > K and left1 < l:
				temp1 = A[left1]
				map1[temp1] -= 1
				if map1[temp1] == 0:
					del map1[temp1]
				left1 += 1
			while len(map2) >= K and left2 < l:
				temp2 = A[left2]
				map2[temp2] -= 1
				if map2[temp2] == 0:
					del map2[temp2]
				left2 += 1
			ans += left2 - left1
			end += 1
		return ans


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		n = len(A)
		hashmap = {}
		l = 0
		count = 0
		ans = 0
		sums = 1
		for r in range(n):
			if A[r] in hashmap:
				hashmap[A[r]] += 1
			else:
				hashmap[A[r]] = 1
			if hashmap[A[r]] == 1:
				count += 1
			while count > K or hashmap[A[l]] > 1:
				if count > K:
					sums = 1
				else:
					sums += 1
				hashmap[A[l]] -= 1
				if hashmap[A[l]] == 0:
					count -= 1
				l += 1
			if count == K:
				ans += sums
		return ans


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def helper(A, K):
			d = defaultdict(int)
			begin = 0
			end = 0
			ans = float('-inf')
			count = 0
			res = 0
			while end < len(A):
				char = A[end]
				d[char] += 1
				if d[char] == 1:
					count += 1
				end += 1
				while count > K:
					temp = A[begin]
					d[temp] -= 1
					if d[temp] == 0:
						count -= 1
					begin += 1
				res += end - begin + 1
			return res
		return helper(A, K) - helper(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: 'List[int]', K: 'int') -> 'int':
		return self.subarraysWithAtMostKDistinct(A, K) - self.subarraysWithAtMostKDistinct(A, K - 1)

	def subarraysWithAtMostKDistinct(self, s, k):
		lookup = collections.defaultdict(int)
		(l, r, counter, res) = (0, 0, 0, 0)
		while r < len(s):
			lookup[s[r]] += 1
			if lookup[s[r]] == 1:
				counter += 1
			r += 1
			while l < r and counter > k:
				lookup[s[l]] -= 1
				if lookup[s[l]] == 0:
					counter -= 1
				l += 1
			res += r - l
		return res


class Window:

	def __init__(self):
		self.num = 0
		self.dic = collections.defaultdict(int)

	def add(self, v: int) -> int:
		if self.dic[v] == 0:
			self.num += 1
		self.dic[v] += 1
		return self.num

	def remove(self, v: int) -> int:
		self.dic[v] -= 1
		if self.dic[v] == 0:
			self.num -= 1
		return self.num

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		wk = Window()
		wm = Window()
		sk = 0
		sm = 0
		e = 0
		ans = 0
		while e < len(A):
			ce = A[e]
			nk = wk.add(ce)
			nm = wm.add(ce)
			if nk < K:
				e += 1
			elif nk == K:
				while nm != K - 1:
					nm = wm.remove(A[sm])
					sm += 1
				ans += sm - sk
				e += 1
			else:
				while nk != K:
					nk = wk.remove(A[sk])
					sk += 1
				while nm != K - 1:
					nm = wm.remove(A[sm])
					sm += 1
				ans += sm - sk
				e += 1
		return ans


class Window:

	def __init__(self):
		self.count = collections.Counter()
		self.nonzero = 0

	def add(self, x):
		self.count[x] += 1
		if self.count[x] == 1:
			self.nonzero += 1

	def remove(self, x):
		self.count[x] -= 1
		if self.count[x] == 0:
			self.nonzero -= 1

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		window1 = Window()
		window2 = Window()
		ans = left1 = left2 = 0
		for x in A:
			window1.add(x)
			window2.add(x)
			while window1.nonzero > K:
				window1.remove(A[left1])
				left1 += 1
			while window2.nonzero >= K:
				window2.remove(A[left2])
				left2 += 1
			ans += left2 - left1
		return ans


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A, K: int) -> int:

		def atMostK(nums, k):
			print(nums, k)
			(res, left) = (0, 0)
			counter = Counter()
			for (right, v) in enumerate(nums):
				if counter[v] == 0:
					k -= 1
				counter[v] += 1
				while k < 0:
					counter[A[left]] -= 1
					if counter[A[left]] == 0:
						k += 1
					left += 1
				res += right - left
			return res
		return atMostK(A, K) - atMostK(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMostK(kk):
			counter = collections.Counter()
			res = ii = 0
			for jj in range(len(A)):
				if counter[A[jj]] == 0:
					kk -= 1
				counter[A[jj]] += 1
				while kk < 0:
					counter[A[ii]] -= 1
					if counter[A[ii]] == 0:
						kk += 1
					ii += 1
				res += jj - ii + 1
			return res
		return atMostK(K) - atMostK(K - 1)


from collections import defaultdict as dd

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		n = len(A)
		i = j = 0
		d = dd(int)
		res = 0
		while j < n:
			while j < n and len(d) < K:
				d[A[j]] += 1
				j += 1
			(i1, j1) = (i, j)
			d[A[i]] -= 1
			while d[A[i]] > 0:
				i += 1
				d[A[i]] -= 1
			while j < n and A[j] in d:
				j += 1
			if len(d) == K:
				res += (i - i1 + 1) * (j - j1 + 1)
			d.pop(A[i])
			i += 1
			j = j1
		return res


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMostK(A, K):
			(ans, curr) = (0, 0)
			cnt = defaultdict(int)
			i = 0
			for (j, num) in enumerate(A):
				if num not in cnt:
					K -= 1
				cnt[num] += 1
				while K < 0:
					cnt[A[i]] -= 1
					if cnt[A[i]] == 0:
						del cnt[A[i]]
						K += 1
					i += 1
				ans += j - i + 1
			return ans
		return atMostK(A, K) - atMostK(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.at_most_K(A, K) - self.at_most_K(A, K - 1)

	def at_most_K(self, A, k):
		left = 0
		counter = collections.Counter()
		diff = 0
		result = 0
		for right in range(len(A)):
			counter[A[right]] += 1
			if counter[A[right]] == 1:
				diff += 1
			while diff > k:
				counter[A[left]] -= 1
				if counter[A[left]] == 0:
					diff -= 1
				left += 1
			result += right - left + 1
		return result


class Solution:

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

	def atMostK(self, A, K):
		count = collections.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


from typing import Dict, Set, List, Tuple
from collections import defaultdict
from pprint import pprint

class Window:

	def __init__(self):
		self._counter = {}
		self._distinct_num = 0

	def add(self, num):
		if num in self._counter:
			self._counter[num] += 1
		else:
			self._distinct_num += 1
			self._counter[num] = 1

	def remove(self, num):
		self._counter[num] -= 1
		if self._counter[num] == 0:
			self._distinct_num -= 1
			del self._counter[num]

	@property
	def nums(self):
		return self._distinct_num

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		w1 = Window()
		w2 = Window()
		x = y = z = 0
		result = 0
		while z < len(A):
			w1.add(A[z])
			w2.add(A[z])
			z += 1
			while w1.nums > K:
				w1.remove(A[x])
				x += 1
			while w2.nums > K - 1:
				w2.remove(A[y])
				y += 1
			if w1.nums == K:
				assert w2.nums == K - 1
			result += y - x
		return result


from collections import defaultdict

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		n = len(A)
		if n < K:
			return 0
		count = defaultdict(int)
		p1 = 0
		p2 = 0
		p3 = 0
		count[A[0]] += 1
		ans = 0
		while p2 < n:
			remaining = K - len(count)
			while remaining > 0:
				p2 += 1
				if p2 == n:
					return ans
				count[A[p2]] += 1
				if count[A[p2]] == 1:
					remaining -= 1
			while p3 < n and A[p3] in count:
				p3 += 1
			while len(count) == K:
				ans += p3 - p2
				p1 += 1
				count[A[p1 - 1]] -= 1
				if count[A[p1 - 1]] == 0:
					del count[A[p1 - 1]]
		return ans


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		checkSet = OrderedDict()
		windowStart = 0
		count = 0
		ans = []
		for (i, n) in enumerate(A):
			checkSet[n] = i
			checkSet.move_to_end(n)
			while len(checkSet) > K:
				windowStart = checkSet.popitem(last=False)[1] + 1
			if len(checkSet) == K:
				count += next(iter(list(checkSet.items())))[1] - windowStart + 1
		return count


class Solution:

	def subarraysWithKDistinct(self, A: List[int], k: int) -> int:
		dic = {}
		n = len(A)
		left = 0
		right = 0
		cnt = 0
		for i in range(n):
			if A[i] in dic:
				dic[A[i]] += 1
			else:
				dic[A[i]] = 1
			l = len(dic)
			if l == k + 1:
				del dic[A[right]]
				right += 1
				left = right
				l -= 1
			if l == k:
				while dic[A[right]] > 1:
					dic[A[right]] -= 1
					right += 1
				cnt += right - left + 1
		return cnt


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		left1 = 0
		left2 = 0
		w1 = {}
		w2 = {}
		count = 0
		for (right, x) in enumerate(A):
			if x in w1:
				w1[x] += 1
			else:
				w1[x] = 1
			if x in w2:
				w2[x] += 1
			else:
				w2[x] = 1
			while len(w1) > K:
				if w1[A[left1]] == 1:
					w1.pop(A[left1])
				elif w1[A[left1]] > 1:
					w1[A[left1]] -= 1
				left1 += 1
			while len(w2) >= K:
				if w2[A[left2]] == 1:
					w2.pop(A[left2])
				elif w2[A[left2]] > 1:
					w2[A[left2]] -= 1
				left2 += 1
			count += left2 - left1
		return count


class Solution:

	def _identify_limit(self, A, current_limit, K, char_count_after_limit):
		temp_char = A[current_limit]
		while char_count_after_limit.get(temp_char, 0) > 1:
			char_count_after_limit[temp_char] = char_count_after_limit[temp_char] - 1
			current_limit += 1
			temp_char = A[current_limit]
		return (current_limit, char_count_after_limit)

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		char_info = {item: [] for item in set(A)}
		unique_char_count = {}
		unique_char = set()
		start_idx = 0
		end_idx = 0
		num_substr = 0
		current_subarray = []
		current_valid_count = 0
		limit_idx = 0
		while end_idx < len(A) + 1:
			if len(unique_char_count) == K:
				(limit_idx, unique_char_count) = self._identify_limit(A, limit_idx, K, unique_char_count)
				num_substr += limit_idx - start_idx + 1
				if end_idx < len(A):
					current_char = A[end_idx]
					unique_char_count[current_char] = unique_char_count.get(current_char, 0) + 1
				end_idx += 1
			elif len(unique_char_count) > K:
				current_char = A[limit_idx]
				unique_char_count.pop(current_char)
				start_idx = limit_idx + 1
				limit_idx = start_idx
			else:
				if end_idx < len(A):
					current_char = A[end_idx]
					unique_char_count[current_char] = unique_char_count.get(current_char, 0) + 1
				end_idx += 1
		return num_substr


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		(d, t) = (defaultdict(int), defaultdict(int))
		(a, b) = (K, K)
		(left, right) = (0, 0)
		res = 0
		for (i, ele) in enumerate(A):
			a -= 1 if d[ele] == 0 else 0
			b -= 1 if t[ele] == 0 else 0
			d[ele] += 1
			t[ele] += 1
			while a < 0:
				a += 1 if d[A[left]] == 1 else 0
				d[A[left]] -= 1
				left += 1
			while b <= 0:
				b += 1 if t[A[right]] == 1 else 0
				t[A[right]] -= 1
				right += 1
			res += right - left
		return res


class Solution:

	def subarraysWithKDistinct(self, A: 'List[int]', K: 'int') -> 'int':
		freq = {}
		start = 0
		start_k = 0
		res = 0
		for (i, x) in enumerate(A):
			freq[x] = freq.get(x, 0) + 1
			if len(freq) == K + 1:
				del freq[A[start_k]]
				start_k += 1
				start = start_k
			if len(freq) == K:
				while freq[A[start_k]] > 1:
					freq[A[start_k]] -= 1
					start_k += 1
				res += start_k - start + 1
		return res


from collections import defaultdict

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		total = 0
		l1 = 0
		l2 = 0
		memo1 = defaultdict(int)
		memo2 = defaultdict(int)
		for (r, c) in enumerate(A):
			memo1[c] += 1
			memo2[c] += 1
			while len(memo1) > K:
				memo1[A[l1]] -= 1
				if memo1[A[l1]] == 0:
					del memo1[A[l1]]
				l1 += 1
			while len(memo2) >= K:
				memo2[A[l2]] -= 1
				if memo2[A[l2]] == 0:
					del memo2[A[l2]]
				l2 += 1
			total += l2 - l1
		return total


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def help(k):
			res = 0
			left = 0
			d = {}
			for (i, ele) in enumerate(A):
				d[ele] = d.get(ele, 0) + 1
				while len(d) > k:
					d[A[left]] -= 1
					if d[A[left]] == 0:
						del d[A[left]]
					left += 1
				res += i - left
			return res
		return help(K) - help(K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atmost(k):
			i = 0
			res = 0
			d = defaultdict(int)
			for (j, a) in enumerate(A):
				if d[a] == 0:
					k -= 1
				d[a] += 1
				while k < 0:
					d[A[i]] -= 1
					if d[A[i]] == 0:
						k += 1
					i += 1
				res += j - i + 1
			return res
		return atmost(K) - atmost(K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMost(A: List[int], K: int) -> int:
			d = collections.defaultdict(int)
			i = ret = 0
			for j in range(len(A)):
				d[A[j]] += 1
				while len(d) > K:
					d[A[i]] -= 1
					if d[A[i]] == 0:
						del d[A[i]]
					i += 1
				ret += j - i + 1
			return ret
		return atMost(A, K) - atMost(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def getAtMost(K):
			freq = defaultdict(int)
			subarray_count = 0
			left = 0
			for (right, num) in enumerate(A):
				freq[num] += 1
				while len(freq) > K:
					freq[A[left]] -= 1
					if freq[A[left]] == 0:
						del freq[A[left]]
					left += 1
				subarray_count += right - left + 1
			return subarray_count
		return getAtMost(K) - getAtMost(K - 1)


from collections import defaultdict

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		if K == 0:
			return 0
		res1 = self.helper(A, K)
		res2 = self.helper(A, K - 1)
		return res1 - res2

	def helper(self, a, k):
		if k == 0:
			return 0
		count = defaultdict(int)
		result = 0
		l = 0
		r = 0
		while r < len(a):
			count[a[r]] += 1
			while len(count) > k:
				count[a[l]] -= 1
				if count[a[l]] == 0:
					count.pop(a[l])
				l += 1
			result += r - l + 1
			r += 1
		return result


class Solution:

	def subarraysWithKDistinct(self, A, K):
		(cnt1, cnt2) = (dict(), dict())
		(res, i1, i2) = (0, 0, 0)
		for v in A:
			cnt1[v] = cnt1.get(v, 0) + 1
			cnt2[v] = cnt2.get(v, 0) + 1
			while len(cnt1) > K:
				cnt1[A[i1]] -= 1
				if cnt1[A[i1]] == 0:
					del cnt1[A[i1]]
				i1 += 1
			while len(cnt2) >= K:
				cnt2[A[i2]] -= 1
				if cnt2[A[i2]] == 0:
					del cnt2[A[i2]]
				i2 += 1
			res += i2 - i1
		return res

class Solution:

	def subarraysWithKDistinct(self, A, K):
		(cnt1, cnt2) = (dict(), dict())
		(res, i1, i2) = (0, 0, 0)
		for v in A:
			cnt1[v] = cnt1.get(v, 0) + 1
			cnt2[v] = cnt2.get(v, 0) + 1
			while len(cnt1) > K:
				X = A[i1]
				cnt1[X] -= 1
				if cnt1[X] == 0:
					del cnt1[X]
				i1 += 1
			while len(cnt2) > K - 1:
				X = A[i2]
				cnt2[X] -= 1
				if cnt2[X] == 0:
					del cnt2[X]
				i2 += 1
			res += i2 - i1
		return res


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.at_most(A, K) - self.at_most(A, K - 1)

	def at_most(self, A, K):
		if K == 0:
			return 0
		window = {}
		left = 0
		ret = 0
		for right in range(len(A)):
			window[A[right]] = window.get(A[right], 0) + 1
			while left < right and len(window) > K:
				window[A[left]] -= 1
				if window[A[left]] == 0:
					del window[A[left]]
				left += 1
			ret += right - left + 1
		return ret


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		res = 0
		left = right = 0
		window = Counter()
		while right < len(A) and len(window) < K:
			window[A[right]] += 1
			right += 1
		if len(window) < K:
			return 0
		while right < len(A) and len(window) == K:
			rmarker = right
			while right < len(A) and A[right] in window:
				right += 1
			rcount = right - rmarker + 1
			lmarker = left
			while window[A[left]] > 1:
				window[A[left]] -= 1
				left += 1
			lcount = left - lmarker + 1
			res += lcount * rcount
			window[A[left]] -= 1
			del window[A[left]]
			left += 1
			right = rmarker
			while right < len(A) and len(window) < K:
				window[A[right]] += 1
				right += 1
		while len(window) == K:
			window[A[left]] -= 1
			res += 1
			if not window[A[left]]:
				del window[A[left]]
			left += 1
		return res


class Solution:

	def helper(self, A, B):
		count = 0
		left = 0
		right = 0
		d = {}
		while right < len(A):
			if A[right] not in d:
				d[A[right]] = 0
			d[A[right]] += 1
			while len(d) > B:
				d[A[left]] -= 1
				if d[A[left]] == 0:
					d.pop(A[left])
				left += 1
			count += right - left + 1
			right += 1
		return count

	def subarraysWithKDistinct(self, A: List[int], B: int) -> int:
		return self.helper(A, B) - self.helper(A, B - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def subarraysWithDictinctAtMost(A: List[int], K: int) -> int:
			(left, right) = (0, 0)
			ans = 0
			counter = dict()
			while right < len(A):
				if A[right] not in counter:
					counter[A[right]] = 0
				counter[A[right]] += 1
				while len(counter) > K:
					counter[A[left]] -= 1
					if counter[A[left]] == 0:
						counter.pop(A[left])
					left += 1
				ans += right - left + 1
				right += 1
			return ans
		return subarraysWithDictinctAtMost(A, K) - subarraysWithDictinctAtMost(A, K - 1)


class Solution:

	def atMostK(self, arr, k):
		d = {}
		(l, r) = (0, 0)
		count = 0
		while r < len(arr):
			if arr[r] not in d:
				d[arr[r]] = 0
			d[arr[r]] += 1
			while len(d) > k:
				d[arr[l]] -= 1
				if d[arr[l]] == 0:
					d.pop(arr[l])
				l += 1
			count += r - l + 1
			r += 1
		return count

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.atMostK(A, K) - self.atMostK(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMost(A, K):
			left = res = 0
			hash_map = {}
			for right in range(len(A)):
				hash_map[A[right]] = hash_map.get(A[right], 0) + 1
				while len(hash_map) > K:
					hash_map[A[left]] -= 1
					if hash_map[A[left]] == 0:
						del hash_map[A[left]]
					left += 1
				res += right - left + 1
			return res
		return atMost(A, K) - atMost(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		n = len(A)
		if n < K:
			return 0
		left = 0
		right = 0
		totalCount = 0
		dp = [0 for i in range(20001)]
		result = 0
		for right in range(n):
			if dp[A[right]] == 0:
				totalCount += 1
			dp[A[right]] += 1
			while totalCount >= K:
				if totalCount == K:
					result += 1
				dp[A[left]] -= 1
				if dp[A[left]] == 0:
					totalCount -= 1
				left += 1
			while totalCount <= K and left > 0:
				left -= 1
				if dp[A[left]] == 0:
					totalCount += 1
				dp[A[left]] += 1
		return result


from collections import defaultdict

class Solution:

	def subarraysWithKDistinct(self, A, K):

		def atMostK(K):
			(cnt, res, i) = (defaultdict(int), 0, 0)
			for (j, val) in enumerate(A):
				cnt[val] += 1
				while len(cnt) > K:
					X = A[i]
					cnt[X] -= 1
					if not cnt[X]:
						cnt.pop(X)
					i += 1
				res += j - i + 1
			return res
		return atMostK(K) - atMostK(K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMost(k):
			counter = collections.defaultdict(int)
			i = res = 0
			for (j, v) in enumerate(A):
				counter[v] += 1
				while len(counter) > k:
					counter[A[i]] -= 1
					if counter[A[i]] == 0:
						del counter[A[i]]
					i += 1
				res += j - i + 1
			return res
		return atMost(K) - atMost(K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.atMost(A, K) - self.atMost(A, K - 1)

	def atMost(self, A, K):
		if K == 0:
			return 0
		(hi, res) = (0, 0)
		n = len(A)
		count = collections.defaultdict(int)
		for lo in range(n):
			while hi < n and (len(count) < K or A[hi] in count):
				count[A[hi]] += 1
				hi += 1
			res += hi - lo
			count[A[lo]] -= 1
			if count[A[lo]] == 0:
				count.pop(A[lo])
		return res


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def at_most_k(arr, k):
			start = 0
			counter = Counter()
			uniques = 0
			res = 0
			for i in range(len(A)):
				counter[A[i]] += 1
				if counter[A[i]] == 1:
					uniques += 1
				while uniques > k:
					counter[A[start]] -= 1
					if counter[A[start]] == 0:
						uniques -= 1
					start += 1
				res += i - start
			return res
		return at_most_k(A, K) - at_most_k(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		keyCounter = defaultdict(int)
		ALen = len(A)
		l = 0
		r = 0
		ans = 0
		KNow = 0
		while r <= ALen:
			if KNow == K:
				ans += 1
				temp = 0
				while r + temp < ALen and keyCounter[A[r + temp]] > 0:
					ans += 1
					temp += 1
				if keyCounter[A[l]] > 0:
					keyCounter[A[l]] -= 1
				if keyCounter[A[l]] == 0:
					KNow -= 1
				l += 1
			elif KNow < K:
				if r == ALen:
					return ans
				if keyCounter[A[r]] == 0:
					KNow += 1
				keyCounter[A[r]] += 1
				r += 1
			else:
				if keyCounter[A[l]] > 0:
					keyCounter[A[l]] -= 1
				if keyCounter[A[l]] == 0:
					KNow -= 1
				l += 1
		return ans


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def longest_with_atmostk(s, k):
			start = 0
			counts = defaultdict(int)
			n_chars = 0
			max_len = 0
			for i in range(len(s)):
				if counts[s[i]] == 0:
					n_chars += 1
				counts[s[i]] += 1
				while n_chars > k:
					if counts[s[start]] > 0:
						counts[s[start]] -= 1
						if counts[s[start]] == 0:
							n_chars -= 1
					start += 1
				max_len += i - start + 1
			return max_len
		return longest_with_atmostk(A, K) - longest_with_atmostk(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.atMost(A, K) - self.atMost(A, K - 1)

	def atMost(self, A, k):
		left = res = 0
		freq = collections.Counter()
		for right in range(len(A)):
			if freq[A[right]] == 0:
				k -= 1
			freq[A[right]] += 1
			while k < 0:
				freq[A[left]] -= 1
				if freq[A[left]] == 0:
					k += 1
				left += 1
			res += right - left + 1
		return res


class Solution:

	def subarraysWithKDistinct(self, A, K):

		def atMostK(A, K):
			count = collections.Counter()
			(res, l, window_count) = (0, 0, 0)
			for (r, c) in enumerate(A):
				if count[c] == 0:
					window_count += 1
				count[c] += 1
				while window_count > K:
					count[A[l]] -= 1
					if count[A[l]] == 0:
						window_count -= 1
					l += 1
				res += r - l + 1
			return res
		return atMostK(A, K) - atMostK(A, K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.helper(A, K) - self.helper(A, K - 1)

	def helper(self, A, K):
		counter = collections.Counter()
		p1 = p2 = 0
		res = 0
		while p2 < len(A):
			if counter[A[p2]] == 0:
				K -= 1
			counter[A[p2]] += 1
			while K < 0:
				counter[A[p1]] -= 1
				if counter[A[p1]] == 0:
					K += 1
				p1 += 1
			p2 += 1
			res += p2 - p1
		return res


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMost(K):
			(res, lo, seen) = (0, 0, Counter())
			for hi in range(len(A)):
				if seen[A[hi]] == 0:
					K -= 1
				seen[A[hi]] += 1
				while K < 0:
					seen[A[lo]] -= 1
					if seen[A[lo]] == 0:
						K += 1
					lo += 1
				res += hi - lo + 1
			return res
		return atMost(K) - atMost(K - 1)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		(counter1, counter2) = (collections.Counter(), collections.Counter())
		slow = fast = res = 0
		for a in A:
			(counter1[a], counter2[a]) = (counter1[a] + 1, counter2[a] + 1)
			while len(counter2) == K:
				counter2[A[fast]] -= 1
				if not counter2[A[fast]]:
					del counter2[A[fast]]
				fast += 1
			while len(counter1) > K:
				counter1[A[slow]] -= 1
				if not counter1[A[slow]]:
					del counter1[A[slow]]
				slow += 1
			res += fast - slow
		return res


import collections

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		counter = collections.defaultdict(int)
		result = 0
		start = startK = 0
		for (high, num) in enumerate(A):
			counter[num] += 1
			if len(counter) == K + 1:
				del counter[A[startK]]
				startK += 1
				start = startK
			if len(counter) == K:
				while counter[A[startK]] > 1:
					counter[A[startK]] -= 1
					startK += 1
				result += startK - start + 1
		return result


class Solution:

	def subarraysWithAtMostK(self, A: List[int], K: int) -> int:
		result = i = 0
		count = collections.Counter()
		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
			result += j - i + 1
		return result

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.subarraysWithAtMostK(A, K) - self.subarraysWithAtMostK(A, K - 1)


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		W1 = Counter()
		W2 = Counter()
		l1 = 0
		l2 = 0
		res = 0
		for i in range(len(A)):
			W1[A[i]] += 1
			W2[A[i]] += 1
			while len(W1) > K:
				W1[A[l1]] -= 1
				if W1[A[l1]] == 0:
					del W1[A[l1]]
				l1 += 1
			while len(W2) > K - 1:
				W2[A[l2]] -= 1
				if W2[A[l2]] == 0:
					del W2[A[l2]]
				l2 += 1
			res += l2 - l1
		return res


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		window1 = Counter()
		window2 = Counter()
		l1 = 0
		l2 = 0
		total = 0
		for (r, c) in enumerate(A):
			window1[c] += 1
			window2[c] += 1
			while len(window1) > K:
				window1[A[l1]] -= 1
				if window1[A[l1]] == 0:
					del window1[A[l1]]
				l1 += 1
			while len(window2) > K - 1:
				window2[A[l2]] -= 1
				if window2[A[l2]] == 0:
					del window2[A[l2]]
				l2 += 1
			total += l2 - l1
		return total


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.atMostK(A, K) - self.atMostK(A, K - 1)

	def atMostK(self, A, k):
		start = 0
		end = 0
		res = 0
		chars = collections.Counter()
		distinct = 0
		while end < len(A):
			if chars[A[end]] == 0:
				distinct += 1
			chars[A[end]] += 1
			while distinct > k:
				chars[A[start]] -= 1
				if chars[A[start]] == 0:
					distinct -= 1
				start += 1
			res += end - start + 1
			end += 1
		return res


class Solution:

	def _identify_limit(self, A, current_limit, K, char_count_after_limit):
		char_count_after_limit = {k: v for (k, v) in char_count_after_limit.items()}
		unique_chars = {i for i in char_count_after_limit if char_count_after_limit[i] > 0}
		while len(unique_chars) == K:
			temp_char = A[current_limit]
			char_count_after_limit[temp_char] = char_count_after_limit[temp_char] - 1
			if char_count_after_limit[temp_char] == 0:
				unique_chars.remove(temp_char)
			current_limit += 1
		char_count_after_limit[A[current_limit - 1]] = char_count_after_limit[A[current_limit - 1]] + 1
		return (current_limit - 1, char_count_after_limit)

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		(counter1, counter2) = (collections.Counter(), collections.Counter())
		slow = fast = res = 0
		for (_, a) in enumerate(A):
			(counter1[a], counter2[a]) = (counter1[a] + 1, counter2[a] + 1)
			while len(counter2) == K:
				counter2[A[fast]] -= 1
				if not counter2[A[fast]]:
					del counter2[A[fast]]
				fast += 1
			while len(counter1) > K:
				counter1[A[slow]] -= 1
				if not counter1[A[slow]]:
					del counter1[A[slow]]
				slow += 1
			res += fast - slow
		return res


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		sum = 0
		begin = 0
		end = 0
		s = collections.defaultdict(int)
		lA = len(A)
		for i in range(lA):
			if len(s) >= K:
				s[A[i]] += 1
				if s[A[i]] > 1:
					newend = end
					while s[A[newend]] > 1:
						s[A[newend]] -= 1
						newend += 1
					end = newend
				else:
					begin = end
					while s[A[begin]] > 1:
						s[A[begin]] -= 1
						begin += 1
					s[A[begin]] -= 1
					begin += 1
					end = begin
					while s[A[end]] > 1:
						s[A[end]] -= 1
						end += 1
				sum += end - begin + 1
			else:
				s[A[i]] += 1
				if len(s) == K:
					while s[A[end]] > 1:
						s[A[end]] -= 1
						end += 1
					sum += end - begin + 1
		return sum


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMostK(k):
			count = Counter()
			ans = left = 0
			for (i, a) in enumerate(A):
				if count[a] == 0:
					k -= 1
				count[a] += 1
				while k < 0:
					count[A[left]] -= 1
					if count[A[left]] == 0:
						k += 1
					left += 1
				ans += i - left + 1
			return ans
		return atMostK(K) - atMostK(K - 1)


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.helper(A, K) - self.helper(A, K - 1)

	def helper(self, A, K):
		currSum = 0
		d = Counter()
		i = 0
		for j in range(len(A)):
			d[A[j]] += 1
			while len(d) > K:
				d[A[i]] -= 1
				if not d[A[i]]:
					del d[A[i]]
				i += 1
			currSum += j - i + 1
		return currSum


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def at_most(x):
			left = 0
			counts = Counter()
			res = 0
			for (right, num) in enumerate(A):
				counts[num] += 1
				while len(counts) > x:
					counts[A[left]] -= 1
					if counts[A[left]] == 0:
						del counts[A[left]]
					left += 1
				res += right - left + 1
			return res
		return at_most(K) - at_most(K - 1)


class Solution:

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

	def atMostK(self, s, k):
		if not s:
			return 0
		N = len(s)
		(left, right) = (0, 0)
		ret = 0
		counter = collections.Counter()
		counter[s[right]] += 1
		while right < N:
			if len(counter) > k:
				counter[s[left]] -= 1
				if counter[s[left]] == 0:
					del counter[s[left]]
				left += 1
			else:
				right += 1
				ret += right - left
				if right < N:
					counter[s[right]] += 1
		return ret


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def at_most(K):
			window = Counter()
			left = right = 0
			res = 0
			while right < len(A):
				window[A[right]] += 1
				while len(window) > K:
					window[A[left]] -= 1
					if not window[A[left]]:
						del window[A[left]]
					left += 1
				res += right - left + 1
				right += 1
			return res
		return at_most(K) - at_most(K - 1)


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		(equalCt, lessCt) = (Counter(), Counter())
		(equalPt, lessPt) = (0, 0)
		res = 0

		def add_to_counter(x, co):
			co[x] += 1

		def subtr_from_counter(x, co):
			co[x] -= 1
			if co[x] == 0:
				del co[x]
		for (right, num) in enumerate(A):
			add_to_counter(num, equalCt)
			add_to_counter(num, lessCt)
			while len(equalCt) > K:
				subtr_from_counter(A[equalPt], equalCt)
				equalPt += 1
			while len(lessCt) >= K:
				subtr_from_counter(A[lessPt], lessCt)
				lessPt += 1
			res += lessPt - equalPt
		return res


from collections import Counter

def subarraysWithAtMostK(arr: list, k: int) -> int:
	start = 0
	counter = Counter()
	res = 0
	for end in range(len(arr)):
		num = arr[end]
		counter[num] += 1
		while len(counter) > k:
			to_remove = arr[start]
			counter[to_remove] -= 1
			if counter[to_remove] == 0:
				del counter[to_remove]
			start += 1
		res += end - start + 1
	return res

def subarraysWithKDistinct(arr: list, k: int) -> int:
	return subarraysWithAtMostK(arr, k) - subarraysWithAtMostK(arr, k - 1)

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return subarraysWithKDistinct(A, K)


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def atMost(A: List[int], K: int):
			cache = collections.Counter()
			(res, i) = (0, 0)
			for j in range(len(A)):
				cache[A[j]] += 1
				while len(cache) > K:
					cache[A[i]] -= 1
					if cache[A[i]] == 0:
						del cache[A[i]]
					i += 1
				res += j - i + 1
			return res
		return atMost(A, K) - atMost(A, K - 1)


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		window = Counter()
		res = 0
		left = right = 0
		while True:
			while right < len(A) and len(window) < K:
				window[A[right]] += 1
				right += 1
			if len(window) < K:
				return res
			j = right
			while j < len(A) and A[j] in window:
				j += 1
			res += j - right + 1
			window[A[left]] -= 1
			if not window[A[left]]:
				del window[A[left]]
			left += 1
		return res


class Window:

	def __init__(self):
		self.counter = Counter()
		self.unique = 0

	def add(self, value: int):
		self.counter[value] += 1
		if self.counter[value] == 1:
			self.unique += 1

	def remove(self, value: int):
		self.counter[value] -= 1
		if self.counter[value] == 0:
			self.unique -= 1

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		window1 = Window()
		window2 = Window()
		left1 = left2 = answer = 0
		for right in A:
			window1.add(right)
			window2.add(right)
			while window1.unique > K:
				window1.remove(A[left1])
				left1 += 1
			while window2.unique >= K:
				window2.remove(A[left2])
				left2 += 1
			answer += left2 - left1
		return answer


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.subarraysWithAtmostKDistinct(A, K) - self.subarraysWithAtmostKDistinct(A, K - 1)

	def subarraysWithAtmostKDistinct(self, A, K):
		(l, r, count, res) = (0, 0, 0, 0)
		hashmap = [0] * 20001
		while r < len(A):
			hashmap[A[r]] += 1
			if hashmap[A[r]] == 1:
				count += 1
			while count > K:
				hashmap[A[l]] -= 1
				if hashmap[A[l]] == 0:
					count -= 1
				l += 1
			res += r - l + 1
			r += 1
		return res


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def remove(m, n):
			if m[n] == 1:
				del m[n]
			else:
				m[n] -= 1
		(m1, m2) = (collections.Counter(), collections.Counter())
		res = 0
		i1 = i2 = -1
		for (i0, n) in enumerate(A):
			while i1 + 1 < len(A) and len(m1) < K:
				i1 += 1
				m1[A[i1]] += 1
			if len(m1) < K:
				return res
			while i2 + 1 < len(A) and len(m2) < K + 1:
				i2 += 1
				m2[A[i2]] += 1
			res += i2 - i1 + int(len(m2) == K)
			remove(m1, n)
			remove(m2, n)
		return res


from collections import Counter

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		return self.subarraysWithAtMostKDistinct(A, K) - self.subarraysWithAtMostKDistinct(A, K - 1)

	def subarraysWithAtMostKDistinct(self, A, K):
		window = Counter()
		j = 0
		res = 0
		for i in range(len(A)):
			c = A[i]
			window[c] += 1
			while len(window) > K:
				last = A[j]
				window[last] -= 1
				if window[last] == 0:
					del window[last]
				j += 1
			res += i - j + 1
		return res


from collections import Counter

def solve(A, K):
	count = Counter()
	front = iter(A)
	ans = 0
	size = 0
	for k in A:
		count[k] += 1
		size += 1
		while len(count) > K:
			key = next(front)
			count[key] -= 1
			size -= 1
			if count[key] == 0:
				del count[key]
		ans += size
	return ans

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		cx = Counter()
		cy = Counter()
		fx = iter(A)
		fy = iter(A)
		sx = 0
		sy = 0
		ans = 0
		for k in A:
			cx[k] += 1
			cy[k] += 1
			sx += 1
			sy += 1
			while len(cx) > K:
				key = next(fx)
				cx[key] -= 1
				sx -= 1
				if cx[key] == 0:
					del cx[key]
			while len(cy) > K - 1:
				key = next(fy)
				cy[key] -= 1
				sy -= 1
				if cy[key] == 0:
					del cy[key]
			ans += sx - sy
		return ans


class Solution:

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

	def atMostK(self, A, K):
		count = collections.Counter()
		res = left = right = distinct = 0
		while right < len(A):
			count[A[right]] += 1
			if count[A[right]] == 1:
				distinct += 1
			while distinct > K:
				count[A[left]] -= 1
				if count[A[left]] == 0:
					distinct -= 1
				left += 1
			res += right - left + 1
			right += 1
		return res


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		(good_start, bad_start) = (-1, -1)
		(good_count, bad_count) = ({}, {})

		def add(count, element):
			if element not in count:
				count[element] = 0
			count[element] += 1

		def remove(count, element):
			count[element] -= 1
			if count[element] == 0:
				del count[element]

		def find_good_start(A, K, cur_pos, index, good_count):
			if len(good_count) == K:
				return index
			cur = index
			while cur < cur_pos and len(good_count) > K:
				cur += 1
				remove(good_count, A[cur])
			return cur
		total = 0
		for i in range(len(A)):
			cur = A[i]
			add(good_count, cur)
			add(bad_count, cur)
			if len(good_count) >= K:
				good_start = find_good_start(A, K, i, good_start, good_count)
				bad_start = find_good_start(A, K - 1, i, bad_start, bad_count)
				if len(good_count) == K and len(bad_count) == K - 1:
					total += bad_start - good_start
		return total


class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
		(m1, m2) = (collections.Counter(), collections.Counter())

		def remove(m, n):
			m[n] -= 1
			if not m[n]:
				del m[n]
		res = 0
		left = right = -1
		for (i, n) in enumerate(A):
			while left < len(A) - 1 and len(m1) < K:
				left += 1
				m1[A[left]] += 1
			if len(m1) < K:
				return res
			while right < len(A) - 1 and len(m2) <= K:
				right += 1
				m2[A[right]] += 1
			res += right - left + (len(m2) == K)
			remove(m1, n)
			remove(m2, n)
		return res


from collections import defaultdict

class Solution:

	def subarraysWithKDistinct(self, A: List[int], K: int) -> int:

		def subArray(k):
			right = 0
			left = 0
			freq = collections.defaultdict(int)
			count = 0
			while right < len(A):
				freq[A[right]] += 1
				right += 1
				while len(freq) > k:
					freq[A[left]] -= 1
					if freq[A[left]] == 0:
						del freq[A[left]]
					left += 1
				count += right - left
			return count
		output = 0
		output += subArray(K) - subArray(K - 1)
		return output