Count all subarrays with at exactly k different elements

at-most-k-diff.md

Interesting problem on sliding window: lc

The idea of solution is to solve a simpler problem - count subarrays with at most K distinct characters. This one is similar to longest substr without repeating characters

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return atMostK(A, K) - atMostK(A, K - 1);
    }
    
    int atMostK(vector<int>& A, int K) {
        int res = 0;
        unordered_map<int,int> freq;
        int l = 0;
        for (int r = 0; r < A.size(); ++r) {
            if (freq[A[r]] == 0)
                --K;
            ++freq[A[r]];
            // get rid of elements from left
            while (K < 0) {
                --freq[A[l]];
                if (freq[A[l]] == 0)
                    ++K;
                ++l;
            }
            // number of subarrays ending at r-th element
            res += r - l + 1;
        }
        
        return res;
    }
};