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);
}
}