🔥#Aditya Verma Sliding Window Template || Khandani Template
Complexity\n- Time complexity:\nO(n) \n\n- Space complexity:\nO(n) \n\n# Code\n\nclass Solution {\npublic:\n    int subarrayCountWithAtMostKchar(vector<int>& ar
# Complexity\n- Time complexity:\n$$O(n)$$ \n\n- Space complexity:\n$$O(n)$$ \n\n# Code\n```\nclass Solution {\npublic:\n    int subarrayCountWithAtMostKchar(vector<int>& arr, int k) {\n\n        ios_base::sync_with_stdio(false);\n        cin.tie(nullptr);\n        cout.tie(nullptr);\n\n        int i = 0, j = 0, count = 0;\n        unordered_map<int, int> mp; // create an unordered map to keep track of the count of each integer\n\n        while (j < arr.size()) {\n            mp[arr[j]]++; // increment the count of integer arr[j] in the map\n\n            if (mp.size() <= k) { // if the number of distinct integers in the map is less than or equal to k\n                count += j - i + 1; // then update the count with the number of subarrays that can be formed with this window\n                j++; // move the right pointer forward\n            } else {\n                while (mp.size() > k) { // if the number of distinct integers in the map is greater than k\n                    mp[arr[i]]--; // decrement the count of the integer arr[i] in the map\n\n                    if (mp[arr[i]] == 0) { // if the count becomes 0\n                        mp.erase(arr[i]); // then remove the integer from the map\n                    }\n\n                    i++; // move the left pointer forward\n                }\n\n                if (mp.size() <= k) { // after shrinking the window, if the number of distinct integers in the map is less than or equal to k\n                    count += j - i + 1; // then update the count with the number of subarrays that can be formed with this window\n                }\n\n                j++; // move the right pointer forward\n            }\n        }\n\n        return count; // return the count\n    }\n\n    \n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        int a = subarrayCountWithAtMostKchar(nums, k); // get the count of subarrays with at most k distinct integers\n        int b = subarrayCountWithAtMostKchar(nums, k - 1); // get the count of subarrays with at most k-1 distinct integers\n\n        return a - b; // the difference between these counts gives the count of subarrays with exactly k distinct integers\n    }\n};\n```
['Array', 'Hash Table', 'Sliding Window', 'Counting', 'C++']