level : simple-easy ;
we can map string to bitset<26> and with a 2 loop O(N1N2(bitset_oper)) for each bitset of N1 and bitset of N2 get OR | to
such bitset and if now bitset.count==26 increase result (1 sec)
my code β CodeChef: Practical coding for everyone
3 Likes
here is my code with complexity O(26*N1)
#include<stdio.h>
int n1,j,k,i,l,n2,s1[10000][26],prev[26],s2[26],min;
long int w;
int main()
{
char a;
scanf("%d%d",&n1,&n2);
scanf("%c",&a);
for(i=0;i<n1;i++)
{
scanf("%c",&a);
while(a!=10){
s1[i][a-65]=1;
scanf("%c",&a);
}
}
for(i=1;i<=n2;i++)
{
scanf("%c",&a);
while(a!=10){
if(prev[a-65]!=i)
{
prev[a-65]=i;
s2[a-65]++;}
scanf("%c",&a);
}
}
for(i=0;i<n1;i++)
{
k=0;min=n2;j=0;
for(l=0;l<26;l++){
if(!s1[i][l]&&s2[l]>=1){
k++;
if(min>s2[l])
min=s2[l];
}
else if (s1[i][l])
j++;
}
if(k+j==26)
w+=min;
}
printf("%ld\n",w); return 0;
}
I was unable to submit my code yesterday so i have uploaded my solution, Donβt know whether it is right or wrong. I think it is right but please help me if it is wrong.