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

Difficulty: interview

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:
        # seems like you need 3 pointers, shink from either side
        ans, ctr, lb, count = 0, {}, 0, 0
        for i, val in enumerate(A): 
            if val not in ctr: 
                ctr[val] = 0
            ctr[val] += 1
            
            # try to code it up first    
            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(): 
                    # recover step, kind of lame
                    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, s: List[int], k: int) -> int:
#         # [1,2,1,2,3], K=2
#         #  ^
#         #    ^
#         #  3
#         n=len(s)
#         if n<k:
#             return 0
        
#         if k==0:
#             return 1
        
#         seen={}
#         cnt=0
        
#         i=0
#         j=0
        
#         while i<n and j<n:
#             if s[j] not in seen:
#                 seen[s[j]]=1
#             else:
#                 seen[s[j]]+=1
            
#             while len(seen)>k:
#                 seen[s[i]]-=1
#                 if not seen[s[i]]:
#                     del seen[s[i]]
#                 i+=1
                
#             seen1=seen.copy()
#             i1=i   
#             while len(seen1)==k:
#                 cnt+=1
#                 seen1[s[i1]]-=1
#                 if not seen1[s[i1]]:
#                     del seen1[s[i1]]
#                 i1+=1
                
#             j+=1

#         return cnt
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 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 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:
        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:
        '''
        1 2 1 2 3
        i       j

        2 1 1 1 2
        i j
        '''
        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:
                # remove the distinct at second, move second, first
                del obj[s[second]]
                second += 1
                first = second
            if len(obj) == K:
                # update second and answer (Notice: K >= 1)
                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):
            # print(\"---------\")
            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
                # print(A[start: i+1])
                ret += i - start + 1
            return ret
        
        # print(subarraysWithAtLeast(K))
        # print(subarraysWithAtLeast(K-1))
        return subarraysWithAtLeast(K) - subarraysWithAtLeast(K-1)

class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        int_dict = {} ## Stores the last appearence of each integer
        int_sorted_list = [] ## List of intergers that have already appeared, in the order of their last appearance
        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)):
                # not in the map,k-=1
                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)
            


# 992. Subarrays with K Different Integers

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    
                    # print(j ,l)
            else:
                if A[j] in cnt:
                    cnt[A[j]] += 1
                    while cnt[A[i]] > 1:
                        cnt[A[i]] -= 1
                        i += 1
                        l += 1
                    # print(j, l)
                    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
                    # print(j, l)
                    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)
            
            # At most K distinct elements
            while len(window1) > K:
                window1.remove(A[left1])
                left1 += 1
            
            # At most K-1 distinct elements
            while len(window2) >= K:
                window2.remove(A[left2])
                left2 += 1
            
            # At most K - At most (K-1) will give you exact K elements
            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:
        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 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 = left1 = left2 = 0

        
        for _, x in enumerate(A):
            #print(right, x)
            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:
    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
            #print(c, l, fr, r)
            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:
          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

class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        
        
        #Important
        #https://leetcode.com/problems/subarrays-with-k-different-integers/discuss/523136/JavaC%2B%2BPython-Sliding-Window
        
        print((self.atmost_counts(A, K), self.atmost_counts(A, K-1)))
        return self.atmost_counts(A, K) - self.atmost_counts(A, K-1)
                
    
    def atmost_counts(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
                
            


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 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 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:
        
        def helper(A,K):

            d = defaultdict(int)
            begin = 0
            end = 0
            ans = float('-inf')
            count = 0
            res = 0
            # move from the right pointer
            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    #the number of subarrays ending with s[r-1] **
        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:
            #print(right, x)
            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
                # print(counter, res)
            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:
            # Step 1: find j1
            while j < n and len(d) < K:
                d[A[j]] += 1
                j += 1
            i1, j1 = i, j
            # Step 2: find i
            d[A[i]] -= 1
            while d[A[i]] > 0:
                i += 1
                d[A[i]] -= 1
            # Step 3: find j
            while j < n and A[j] in d:
                j += 1
            if len(d) == K:
                res += (i-i1+1)*(j-j1+1)
            # print(i1, i, j1, j)
            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
        # w1 中包含 A[x:z] 中所有的数字，而且 w1 中不重合的数字数量为 K
        # w2 中包含 A[y:z] 中所有的数字，而且 w2 中不重合的数字数量为 K - 1
        # if x <= i < y; then A[i:z] 中的不重合的数字数量为 K

        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
        
        # 3 pointer sliding window
        # p1 points to the 1st unique integer, start of the window
        # p2 points to the first occurrance of the Kth unique integer after p1
        # p3 points the the first occurrance of the next unique integer after p2, of end of string at n
        # Given such a window, we add (p3-p2) to the count
        # Then move p1 by 1. Check if that reduces the number of integers to K-1. If no, add p3-p2 again.
        # If yes, then move p2 until the count goes up to K again. If p2 lands on p3 when doing this,
        # then need to move p3 to the next integer. If p3 is already at EOS, return
        
        # To maintain the number of unique integers in a window, we'll use a hashmap
        # Be careful, we need this dict to contain only nonzero count entries. So if a count becomes zero, delete it!
        count = defaultdict(int)
        p1 = 0; p2 = 0; p3 = 0
        count[A[0]] += 1
        ans = 0
        while p2 < n:  # IMP!!! note the <=, not < 
            # Move p2 until the number of unique integers in the window hits K
            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
            # p2 now points to the first instance of the Kth integer after p1
            # Now move p3 to the next unique integer after p2
            # print(\"count: {}, A[{}]: {}, {}\".format(count, p3, A[p3], A[p3] in count))
            while p3 < n and A[p3] in count:
                p3 += 1
            # p3 is either n or points to the (K+1)th integer after p1
            # Now, keep adding (p3-p2) to the count and advancing p1 until we no longer have K integers in this window
            while len(count) == K:
                ans += (p3-p2)
                # print(\"p1:{}, p2:{}, p3:{}, count:{}\".format(p1, p2, p3, count))
                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

from collections import defaultdict
class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        n = len(A)
        if n < K:
            return 0
        
        # 3 pointer sliding window
        # p1 points to the 1st unique integer, start of the window
        # p2 points to the first occurrance of the Kth unique integer after p1
        # p3 points the the first occurrance of the next unique integer after p2, of end of string at n
        # Given such a window, we add (p3-p2) to the count
        # Then move p1 by 1. Check if that reduces the number of integers to K-1. If no, add p3-p2 again.
        # If yes, then move p2 until the count goes up to K again. If p2 lands on p3 when doing this,
        # then need to move p3 to the next integer. If p3 is already at EOS, return
        
        # To maintain the number of unique integers in a window, we'll use a hashmap
        # Be careful, we need this dict to contain only nonzero count entries. So if a count becomes zero, delete it!
        count = defaultdict(int)
        p1 = 0; p2 = 0; p3 = 0
        count[A[0]] += 1
        ans = 0
        while p3 <= n:  # IMP!!! note the <=, not < 
            # Move p2 until the number of unique integers in the window hits K
            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
            # p2 now points to the first instance of the Kth integer after p1
            # Now move p3 to the next unique integer after p2
            # print(\"count: {}, A[{}]: {}, {}\".format(count, p3, A[p3], A[p3] in count))
            while p3 < n and A[p3] in count:
                p3 += 1
            # p3 is either n or points to the (K+1)th integer after p1
            # Now, keep adding (p3-p2) to the count and advancing p1 until we no longer have K integers in this window
            while len(count) == K:
                ans += (p3-p2)
                # print(\"p1:{}, p2:{}, p3:{}, count:{}\".format(p1, p2, p3, count))
                p1 += 1
                count[A[p1-1]] -= 1
                if count[A[p1-1]] == 0:
                    del count[A[p1-1]]
        return ans

class Solution:
    
    def _identify_limit(self, A, current_limit, K,  char_count_after_limit):
        # unique_chars = {i for i in char_count_after_limit if char_count_after_limit[i] > 0}
        # print(unique_chars)
        temp_char = A[current_limit]
        while char_count_after_limit.get(temp_char, 0) > 1 : 
            # print(\"WHILE\", char_count_after_limit)
            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 
        # In any valid subarray what is the index upto which left index could be moved without making subarray bad 
        # Whenever end_idx is moved to right keeping subarray good compute limit_idx again 
        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: 
                # Remove limit_idx from stats
                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

    
    
    #         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:
        
        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:
                # remove the distinct at start_k, move start_k, start
                del freq[A[start_k]]
                start_k += 1
                start = start_k
            if len(freq) == K:
                # update start_k and res (Notice: K >= 1)
                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
            


from collections import defaultdict
class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        n = len(A)
        if n < K:
            return 0
        
        # 3 pointer sliding window
        # p1 points to the 1st unique integer, start of the window
        # p2 points to the first occurrance of the Kth unique integer after p1
        # p3 points the the first occurrance of the next unique integer after p2, of end of string at n
        # Given such a window, we add (p3-p2) to the count
        # Then move p1 by 1. Check if that reduces the number of integers to K-1. If no, add p3-p2 again.
        # If yes, then move p2 until the count goes up to K again. If p2 lands on p3 when doing this,
        # then need to move p3 to the next integer. If p3 is already at EOS, return
        
        # To maintain the number of unique integers in a window, we'll use a hashmap
        # Be careful, we need this dict to contain only nonzero count entries. So if a count becomes zero, delete it!
        count = defaultdict(int)
        p1 = 0; p2 = 0; p3 = 0
        count[A[0]] += 1
        ans = 0
        while p2 < n:  # IMPORTANT: Use p2 rather than p3, because we want to execute as long as p2 can expand, even if p3 is already at n
            # Move p2 until the number of unique integers in the window hits K
            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
            # p2 now points to the first instance of the Kth integer after p1
            # Now move p3 to the next unique integer after p2
            # print(\"count: {}, A[{}]: {}, {}\".format(count, p3, A[p3], A[p3] in count))
            while p3 < n and A[p3] in count:
                p3 += 1
            # p3 is either n or points to the (K+1)th integer after p1
            # Now, keep adding (p3-p2) to the count and advancing p1 until we no longer have K integers in this window
            while len(count) == K:
                ans += (p3-p2)
                # print(\"p1:{}, p2:{}, p3:{}, count:{}\".format(p1, p2, p3, count))
                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:
        
        
        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:
        if K > len(A):
            return 0
        
        result = checker = windowStart = 0
        hashMap = {}
        a_length = len(A)
        
        for windowEnd in range(a_length):
                curr_digit = A[windowEnd]
                if curr_digit in hashMap:
                    hashMap[curr_digit] += 1
                else:
                    hashMap[curr_digit] = 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

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


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:
            # Step 1: find j1
            while j < n and len(d) < K:
                d[A[j]] += 1
                j += 1
            i1, j1 = i, j
            # Step 2: find i
            d[A[i]] -= 1
            while d[A[i]] > 0:
                i += 1
                d[A[i]] -= 1
            # Step 3: find j
            while j < n and A[j] in d:
                j += 1
            if len(d) == K:
                res += (i-i1+1)*(j-j1+1)
            print(i1, i, j1, j)
            d.pop(A[i])
            i += 1
            j = j1
        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:
        dd = {}
        first_uni = 0
        start = 0
        re = 0
        
        for i in range(len(A)):
            dd[A[i]] = dd.get(A[i], 0) + 1
            
            if len(dd) == K + 1:
                dd.pop(A[first_uni])
                first_uni += 1
                start = first_uni
                
            if len(dd) == K:
                while dd[A[first_uni]] > 1:
                    dd[A[first_uni]] -= 1
                    first_uni += 1
                re += first_uni - start + 1
            
        return re


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:
        result = 0
        i, j = 0, 0
        cnt = collections.Counter()
        l = 0
        n = len(A)
        while j < n:
            cnt[A[j]] += 1
            j += 1
            if len(cnt) == K:
                l = 1
                while cnt[A[i]] > 1:
                    cnt[A[i]] -= 1
                    i += 1
                    l += 1
                result += l    
                break
        while j < n:
            if A[j] not in cnt:
                cnt.pop(A[i])
                i += 1
                l = 1
            cnt[A[j]] += 1
            while cnt[A[i]] > 1:
                cnt[A[i]] -= 1
                i += 1
                l += 1
            # print(j, l)
            result += l
            j += 1
        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
        
        # 3 pointer sliding window
        # p1 points to the 1st unique integer, start of the window
        # p2 points to the first occurrance of the Kth unique integer after p1
        # p3 points the the first occurrance of the next unique integer after p2, of end of string at n
        # Given such a window, we add (p3-p2) to the count
        # Then move p1 by 1. Check if that reduces the number of integers to K-1. If no, add p3-p2 again.
        # If yes, then move p2 until the count goes up to K again. If p2 lands on p3 when doing this,
        # then need to move p3 to the next integer. If p3 is already at EOS, return
        
        # To maintain the number of unique integers in a window, we'll use a hashmap
        # Be careful, we need this dict to contain only nonzero count entries. So if a count becomes zero, delete it!
        count = defaultdict(int)
        p1 = 0; p2 = 0; p3 = 0
        count[A[0]] += 1
        ans = 0
        while p2 < n:
            # Move p2 until the number of unique integers in the window hits K
            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
            # p2 now points to the first instance of the Kth integer after p1
            # Now move p3 to the next unique integer after p2
            # print(\"count: {}, A[{}]: {}, {}\".format(count, p3, A[p3], A[p3] in count))
            while p3 < n and A[p3] in count:
                p3 += 1
            # p3 is either n or points to the (K+1)th integer after p1
            # Now, keep adding (p3-p2) to the count and advancing p1 until we no longer have K integers in this window
            while len(count) == K:
                ans += (p3-p2)
                # print(\"p1:{}, p2:{}, p3:{}, count:{}\".format(p1, p2, p3, count))
                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:

        def longest_with_atmostk(s,k):
            start=0
            counts=defaultdict(int) #keep count of each character
            n_chars=0 #store the length of the string from start to current index
            max_len=0 #maximum possible length
            for i in range(len(s)):
                if counts[s[i]]==0: #if the character is never seen before increase length of the current string

                    n_chars+=1 
                counts[s[i]]+=1  #increase the count of the current character
                while n_chars>k: #if there is no repeating characters the length of the string should be i-start+1
                    if counts[s[start]]>0: #if the start 
                        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):
        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
        
        


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, 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:
        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)

class Solution:
    def subarraysWithKDistinct(self, A, K):
        def atMostK(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
        
        return atMostK(K) - atMostK(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):
        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


import collections
class Solution:
    def atMostK(self, A, K):
        count = collections.Counter()
        i, ans = 0, 0 # i is left pointer of window, j is right
        for j in range(len(A)):
            if count[A[j]] == 0:
                K -= 1  # K keeps track of # of different chars in the window
            count[A[j]] += 1
            while K < 0: # when there are too many different chars, contract window
                count[A[i]] -= 1
                if count[A[i]] == 0: # when A[i] is no longer in the window
                    K += 1
                i += 1
            ans += j - i + 1 # for each new A[j], we add j - i + 1 substrings
        return ans
        
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        return self.atMostK(A, K) - self.atMostK(A, K - 1)
        
        
    # exactly(K) = atMost(K) - atMost(K-1)
    # why j - i + 1? For [a, b, c, d] and K = 3, for atMostK, a -> [a], b -> [b], [a, b], c -> [c], [b, c], [a, b, c], d -> [d], [c, d], [b, c, d] every time we look at a new item we add the length of window to total count


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}
        # print(unique_chars)
        while len(unique_chars) == K : 
            # print(\"WHILE\", char_count_after_limit)
            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:
        # 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 
        # # In any valid subarray what is the index upto which left index could be moved without making subarray bad 
        # # Whenever end_idx is moved to right keeping subarray good compute limit_idx again 
        # limit_idx = 0
        # while end_idx < len(A) + 1 : 
        #     if len(unique_char) == K : 
        #         # temp_unique_char = {i for i in unique_char}
        #         # temp_char_count = {k:v for k, v in unique_char_count.items()}
        #         # temp_start_idx = start_idx 
        #         # while len(temp_unique_char) == K:
        #         #     temp_char = A[temp_start_idx]
        #         #     temp_char_count[temp_char] = temp_char_count[temp_char] - 1
        #         #     if temp_char_count[temp_char] == 0: 
        #         #         temp_unique_char.remove(temp_char)
        #         #     temp_start_idx += 1
        #         #     num_substr += 1
        #         # if end_idx < len(A):
        #         #     current_char = A[end_idx]
        #         #     unique_char.add(current_char)
        #         #     unique_char_count[current_char] = unique_char_count.get(current_char, 0) + 1
        #         # print(\"PREV\", unique_char_count)
        #         limit_idx, unique_char_count = self._identify_limit(A, limit_idx, K, unique_char_count)
        #         num_substr += limit_idx - start_idx + 1
        #         # print(start_idx, limit_idx, end_idx- 1)
        #         # print(unique_char_count)
        #         if end_idx < len(A):
        #             current_char = A[end_idx]
        #             unique_char.add(current_char)
        #             unique_char_count[current_char] = unique_char_count.get(current_char, 0) + 1
        #         end_idx += 1 
        #     elif len(unique_char) > K: 
        #         # Remove limit_idx from stats
        #         current_char = A[limit_idx]
        #         unique_char.remove(current_char)
        #         unique_char_count[current_char] = 0
        #         start_idx = limit_idx + 1
        #         limit_idx = start_idx 
        #     else: 
        #         if end_idx < len(A):
        #             current_char = A[end_idx]
        #             unique_char.add(current_char)
        #             unique_char_count[current_char] = unique_char_count.get(current_char, 0) + 1
        #         end_idx += 1 
        # return num_substr
        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, K):
        return self.atMostK(A, K - 1) - self.atMostK(A, K)

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

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)

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):
        ctr = collections.Counter()
        res = i = 0
        for j in range(len(A)):
            if ctr[A[j]] == 0:
                K -= 1
            ctr[A[j]] += 1
            while K < 0:
                ctr[A[i]] -= 1
                if ctr[A[i]] == 0:
                    K += 1
                i += 1
            res += j - i + 1
        return res
        
#         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 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
#         mapp={}
#         n=len(A)
#         j=0
#         ans=0
        
#         for i,c in enumerate(A):
#             mapp[c]=i # last position of c
#             while (len(mapp)>K):
#                 if j==mapp[A[j]]:
#                     del mapp[A[j]]
#                 j+=1
#             ans+=i-j+1
#         return ans


class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        # exactly k = at most k - at most k - 1
        
        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

        # more than k distinct numbers
        # need to shrink
        while len(counter) > k:
            to_remove = arr[start]
            counter[to_remove] -= 1
            if counter[to_remove] == 0:  # remove if frequency reduces to zero
                del counter[to_remove]
            start += 1

        res += end - start + 1

    return res


def subarraysWithKDistinct(arr: list, k: int) -> int:
    # exactly k => atmost(k) - atmost(k - 1)
    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:
        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
            res += p2 - p1 + 1
            p2 += 1
        print(counter)
        return res

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
            # print(j, i)
            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
    '''
        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
    '''

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

import collections

class Window:
    def __init__(self):
        self.num = 0
        self.dic = collections.Counter()
        
    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 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):
            # print((i, n))
            while left < len(A) - 1 and len(m1) < K:
                left += 1
                m1[A[left]] +=1
            
            # print('left, m1', left, m1)
            if len(m1) < K:
                return res
            
            while right < len(A) - 1 and len(m2) <= K:
                right += 1
                m2[A[right]] += 1
            # print('right, m2', right, m2)
            
            res += right - left + (len(m2) == K)
            # print(A[left:right + 1], 'left, right', left, right, res)
            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


from collections import Counter

def solve(A, K):
    count = Counter()
    front = iter(A)
    size = 0
    
    ans = 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)