# Pastry flavors (CRCFLAV)

Find the longest subarray which is not having at least one of the total flavors. If there are 4 flavors available, any subarray with 1,2 or 3 flavors is a valid candidate for our answer.

Explanation

Maintain a map/array for keeping a count of total number of elements from each flavor within the subarray and also maintain a start index which will indicate the starting point of our window. Go through each subarrays that has at least 1 missing flavor and record the maximum size amongst all. And every time K turns to 0 we need to increase the K count back to 1 and here we start sliding our window. The start index will move towards the right along with removing the element from its old position from our map/array until K is back to 1.

Complexity

Time : O(n)
Space : O(n)

``````public static void main (String[] args) throws java.lang.Exception
{

Scanner s = new Scanner(System.in);

int t = s.nextInt();

while(t-- > 0) {

int n = s.nextInt(), k = s.nextInt();

int [] arr = new int[n];

for(int i=0;i<n;++i) {

arr[i] = s.nextInt();
}

int [] map = new int[k+1];

int max = 0, start = 0;

for(int i=0;i<arr.length;++i) {

if(map[arr[i]]++ == 0) --k;

while(k == 0) {

if(--map[arr[start++]] == 0) ++k;
}

if(k > 0) max = Math.max(max,i-start+1);
}

System.out.println(max);
}
}``````