I tried a tactical brute force approach and it passed all the test cases for the problem NOTALLFL.
Problem Link-CodeChef: Practical coding for everyone
Though according to the constraints, a O(N^2) solution shouldn’t pass.
Here is my solution-
I start checking all the subsegments starting from 0th index and going till N minus the length of the longest subsegment found till that time.For each subsegment I take an empty array named freq of length k initialized to 0 and a variable sum. If the element corresponding to the element of array a in the array freq is 0, I increment sum.So sum basically stores the number of new values encountered in the subsegment. Now when sum becomes equal to the value k before the inner loop ends,I break from the inner loop.
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long int
int main()
{ ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];
int sub=k-1,sum=0;
for(int i=0;i<n-sub;i++)
{ int f[k]={0},sum=0,len=0;
for(int j=i;j<n;j++)
{
if(f[a[j]-1]==0)
{
sum++;
}
if(sum==k)
break;
f[a[j]-1]=1;
len++;
if(len>sub)
sub=len;
}
}
cout<<sub<<'\n';
}
}
Please update the test cases if possible. I spent many days thinking of a better solution than a O(N^2) one but after not being able to come up with a better solution I tried the O(N^2) approach. Though it passed but it shouldn’t have.