1
/*
2
    https://leetcode.com/problems/subarrays-with-k-different-integers/submissions/
3

4
    We use a different problem to solve this. We find the number of substrings
5
   with atmost K unique chars. substrings with exactly k = atmost unique (K) -
6
   atmost unique (K-1) This diff only leaves the substrings with exactly k
7
   unique chars
8
*/
9
class Solution {
10
 public:
11
  // Finds the substring with atmost K unique chars
12
  int atmostK(vector<int> &arr, int K) {
13
    int i = 0, j = 0, substrings = 0;
14
    unordered_map<int, int> freq;
15
    const int N = arr.size();
16

17
    while (i < N) {
18
      // Expand the window
19
      if (K >= 0) {
20
        ++freq[arr[i]];
21
        if (freq[arr[i]] == 1) --K;
22
        ++i;
23
      }
24
      // make the window valid
25
      while (K < 0) {
26
        --freq[arr[j]];
27
        if (freq[arr[j]] == 0) ++K;
28
        ++j;
29
      }
30
      // Each valid window adds the subarrays which satisfies the condition
31
      // For : 1,2,1, k=2
32
      // 1: [1]
33
      // 2: [2], [1,2]
34
      // 3: [1,2], [2,1], [1,2,1]
35
      substrings += i - j + 1;
36
    }
37
    return substrings;
38
  }
39

40
  int subarraysWithKDistinct(vector<int> &arr, int K) {
41
    return atmostK(arr, K) - atmostK(arr, K - 1);
42
  }
43
};