PYTHON SOL || FASTER THAN 99.59% || SIMPLE || EXPLAINED || SLIDING WINDOW || LINEAR TIME ||
TIME AND SPACE USED\nRuntime: 378 ms, faster than 99.59% of Python3 online submissions for Subarrays with K Different Integers.\nMemory Usage: 16.6 MB, less tha
# TIME AND SPACE USED\nRuntime: 378 ms, faster than 99.59% of Python3 online submissions for Subarrays with K Different Integers.\nMemory Usage: 16.6 MB, less than 85.54% of Python3 online submissions for Subarrays with K Different Integers.\n\n# EXPLANATION\n```\nWe are going to use sliding window\n\nIn sliding window we keep a window which satisfies the problem\n\nso we are going to keep a subarry in which there will at exactly k unique integers\n\nNow since we have got our subarray say [ 1 , 2 ,1 , 2 , 3 ] and say k = 3\nMy subarray window satisfies the problem\nNow the next step is to try to shrink the window from left\nWhat if I remove 1 [  2 , 1 , 2 ,3 ] still have 3 unique int\nWhat if I remove 2 [ 1 , 2  , 3 ] still have 3 unique int\n\nSo how does this works exactly ??\n\nSee when I am removing 1 from start I know that it is not the latest occurence of 1 i.e. 1 occured after that index which means even if I remove this one I still have 1 in my sliding window somewhere\n\nWhat If I remove 1 [ 2, 3] will have only 2 unique int\nThis time this 1 was the latest occurence of 1 so when we removed this 1 we lost 1 in sliding window \n\nSo this gives the Idea to store latest of occurence of every int\n\nNow when we get sliding window with more than k unique int:\n   We start removing from left and will remove until we remove all occurence of any integer\n   specifically saying when latest[nums[index_start]] = index_start\n   \n   \n\n```\n# IMAGE\n![image](https://assets.leetcode.com/users/images/0aa4fcae-07fe-4cf9-89ba-f62fa4baec0c_1651141645.2300825.png)\n\n\n# CODE\n```\nclass Solution:\n    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n        ans = 0\n        n = len(nums)\n        latest = {}\n        unique = 0\n        prev = 0\n        for i in range(n):\n            if nums[i] not in latest:\n                unique += 1\n            latest[nums[i]] = i\n            if unique > k :\n                while True:\n                    if latest[nums[prev]] == prev:\n                        latest.pop(nums[prev])\n                        prev += 1\n                        unique -= 1                        \n                        break\n                    else:\n                        prev += 1\n                        \n            if unique == k:\n                ans += 1\n                tmp = prev\n                while True:\n                    if latest[nums[tmp]] != tmp:\n                        ans += 1\n                        tmp += 1\n                    else:\n                        break\n        return ans\n                \n                \n```
['Sliding Window', 'Python', 'Python3']