I was solving 1741E — Sending a Sequence Over the Network[problem:1778C] and the editorial mentioned that one of the possible approaches of solving it involves bitmasking. I was able to code it using some parts of the code from another backtracking approach(one which has been mentioned in the editorial), my approach was to make a mask for the all the characters which have been pushed into the set and then proceed via the editorial code. However it isn't working. Can someone help me find the problem. Here is the code.↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define int long long ↵
using namespace std;↵
↵
int min(int a,int b){↵
if(a<b)return a;↵
return b;↵
}↵
int max(int a,int b){↵
if(a>b)return a;↵
return b;↵
}↵
↵
void answer(){↵
int t=1;cin>>t;↵
while(t--){↵
int n,k;cin>>n>>k;↵
string a,b;cin>>a>>b;↵
unordered_set<int>uniq;↵
for(auto it : a){↵
uniq.insert(it);↵
}↵
string list;↵
for(auto it : uniq){↵
list.push_back(it);↵
}↵
k=min(k,uniq.size());↵
int ans=0;↵
for(int mask=0;mask<=(1<<k);mask++){↵
if(__builtin_popcount(mask)==k){↵
int mark[26];↵
memset(mark,0,sizeof mark);↵
for(int i=0;i<k;i++){↵
if((1<<i)&mask){↵
mark[list[i]-'a']=1;↵
}↵
}↵
ll tot_pair=0,match_count=0;↵
for(ll i=0;i<a.size();i++) {↵
if(a[i]==b[i] || mark[a[i]-'a'])↵
match_count++;↵
else {↵
tot_pair+=match_count*(match_count+1)/2;↵
match_count=0;↵
}↵
}↵
tot_pair+=match_count*(match_count+1)/2;↵
ans=max(ans,tot_pair);↵
}↵
}↵
cout<<ans<<endl;↵
}↵
return ;↵
}↵
int32_t main(){↵
answer();↵
} ↵
↵
~~~~~↵
↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define int long long ↵
using namespace std;↵
↵
int min(int a,int b){↵
if(a<b)return a;↵
return b;↵
}↵
int max(int a,int b){↵
if(a>b)return a;↵
return b;↵
}↵
↵
void answer(){↵
int t=1;cin>>t;↵
while(t--){↵
int n,k;cin>>n>>k;↵
string a,b;cin>>a>>b;↵
unordered_set<int>uniq;↵
for(auto it : a){↵
uniq.insert(it);↵
}↵
string list;↵
for(auto it : uniq){↵
list.push_back(it);↵
}↵
k=min(k,uniq.size());↵
int ans=0;↵
for(int mask=0;mask<=(1<<k);mask++){↵
if(__builtin_popcount(mask)==k){↵
int mark[26];↵
memset(mark,0,sizeof mark);↵
for(int i=0;i<k;i++){↵
if((1<<i)&mask){↵
mark[list[i]-'a']=1;↵
}↵
}↵
ll tot_pair=0,match_count=0;↵
for(ll i=0;i<a.size();i++) {↵
if(a[i]==b[i] || mark[a[i]-'a'])↵
match_count++;↵
else {↵
tot_pair+=match_count*(match_count+1)/2;↵
match_count=0;↵
}↵
}↵
tot_pair+=match_count*(match_count+1)/2;↵
ans=max(ans,tot_pair);↵
}↵
}↵
cout<<ans<<endl;↵
}↵
return ;↵
}↵
int32_t main(){↵
answer();↵
} ↵
↵
~~~~~↵
↵
