package question;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question992 {
 public static void main(String[] args) {

 }

 public int subarraysWithKDistinct(int[] A, int K) {
 return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);
 }

 private int atMostKDistinct(int[] a, int k) {
 int left = 0;
 int right = 0;
 int res = 0;
 int[] map = new int[a.length+1];
 int size = 0;

 while (right < a.length) {
 if (map[a[right]]++==0) size++;
 right++;
 while (size>k) {
 if (--map[a[left]]==0) size--;
 left++;
 }
 res+=right-left;
 }
 return res;
 }


 // time out
 public int subarraysWithKDistinct2(int[] A, int K) {
 int res = 0;
 int[] map = new int[A.length + 1];
 int size = 0;
 for (int i = 0; i < K; i++) {
 if (map[A[i]]++ == 0) size++;
 }
 if (size == K) res++;
 int n = A.length - K;
 for (int i = 0; i < n; i++) {
 int[] tmp = Arrays.copyOf(map, map.length);
 int tmpSize = size;
 for (int j = K + i; j < A.length; j++) {
 if (map[A[j]]++ == 0) size++;
 if (size == K) res++;
 else if (size > K) break;
 }
 if (--tmp[A[i]] == 0) tmpSize--;
 if (tmp[A[i + K]]++ == 0) tmpSize++;
 map = tmp;
 size = tmpSize;
 if (size == K) res++;
 }
 return res;
 }


}