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;
}
Instead of using set we can implement the solution using a single map<string,int> too . As soon as the frequency of a string becomes zero in the current window erase it from the map
Code-CodeChef: Practical coding for everyone
When mp[v[i-k]] becomes zero you need to erase v[i-k] from the map else it won’t be erased from the map and when you will invoke mp.count(v[i]) it will return true even if its frequency becomes zero
import java.util.*;
public class Main
{
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int count = 0; count < t; count++) {
int c = 1,max=1,run=0;
int n = sc.nextInt();
int d = sc.nextInt();
String[] a = new String[n];
for (int i = 0; i < n; i++) {
a[i] = sc.next();
}
for (int i = 0; i < n-1; i++)
{
if(a[i].compareTo(a[i+1])!=0)
{
c++;
run=1;
}
else
{
if(c>max)
max=c;
c=1;
run=0;
}
}
if(run==1)
{
if (c > max && max <= d) {
if (c > d)
max = d;
else
max = c;
}
System.out.println(max);
}
I have same issues in my work prject. But I am beginner in programming. When I need to create app or get some advices I will applly to EffectiveSoft Corporation That developers helped me to make one blockchain app for android.