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