# PROBLEM LINK:

*Author:* Shriram Chandran

*Editorialist:* Shriram Chandran

# DIFFICULTY:

Medium

# PREREQUISITES:

Data Structures.

# PROBLEM:

Given a set of strings of size N, find the contiguous subset of size d with largest number of distinct elements.

# EXPLANATION:

The problem is straightforward, the challenge just lies in the implementation.

We need a data structure that can store count of an element in O(logN) or faster, and insert and delete elements in O(logN) or faster.

For this, we use a set to store unique sorted values and a map to store frequency together. For the first d elements, we put them all in the set and store their frequency in the map. We initialise ans as the size of the set. From the next element, we add the current element at position i and increase it’s frequency, and we decrease the count of the element that was at position i-d. If the frequency is 0 on decreasing, we delete that value from the set.

At every step, we keep updating the value ans by set size if the set size is greater, since the answer is just the maximum size of set at any point.

# SOLUTION:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n,d;
cin>>n>>d;
vector<string> e(n,"");
map<string,int> m;
set<string> events;
for(int i=0;i<d;i++)
{
cin>>e[i];
m[e[i]]++;
events.insert(e[i]);
}
int ans=events.size();
for(int i=d;i<n;i++)
{
m[e[i-d]]--;
if(m[e[i-d]]==0)
events.erase(e[i-d]);
cin>>e[i];
m[e[i]]++;
events.insert(e[i]);
if(events.size()>ans)
ans=events.size();
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
```