Problem Statement

Contest Source

*Author, Tester and Editorialist* - Rohail Alam

# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Implementation using two-pointer approach

# PROBLEM:

We seek to find the longest continuous sub-segment in a given array which satisfies the given condition, i.e at least certain number of designs should not occur in the sub-segment.

# EXPLANATION:

This question can be solved with the help of a two pointer approach. The first pointer can go on adding elements to our optimal array, and at the moment when the number of unique elements in the array exceeds D - K (As \geq K designs should be left out) , we use a second pointer to continuously remove elements from our optimal array until the condition is satisfied (which is the number of elements in the array \leq D-K

# SOLUTION:

## C++ Solution

```
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,d,k;
cin>>n>>d>>k;
vector<int> a(n);
for(int i=0;i<n;++i) cin>>a[i];
int ptr1 = 0,ptr2 = 0;
map<int,int> mpp;
int maxy = 0;
if(d == k){
cout<<0<<endl;
continue;
}
while(ptr1 < n){
mpp[a[ptr1]]++;
if(sz(mpp) == d+1-k){
while(sz(mpp) == d+1-k && ptr2 < ptr1){
mpp[a[ptr2]]--;
if(mpp[a[ptr2]] == 0) mpp.erase(a[ptr2]);
ptr2++;
}
}
maxy = max(maxy, ptr1-ptr2+1);
ptr1++;
}
cout<<maxy<<endl;
}
}
```