bro avoid using set use vector and then check your logic .
2 Solutions
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
#define FOR(i, n) for(int i=0; i<(n); i++)
#define FORA(i, a, n) for(int i = a; i <= (n); ++i)
#define FORD(i, a, n) for(int i = a; i >= (n); --i);
#define mod 1000000007
#define pi 2acos(0.0)
#define MP make_pair
#define PB push_back
#define EB emplace_back // its's faster than push_back
#define F first
#define S second
#define sz(x) (int)(x).size()
#define what_is(x) cerr << #x << "is" << x << endl;
#define gcd(a, b) __gcd(num1 , num2)
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
// Method 1 - > Traverse k from k = 1 till k_max;
while(t--) {
string s,r; cin >> s >> r;
int n = s.length();
if(s==r) {
cout << 0 << '\n';
continue;
}
int i = 0;
while(i < n) {
if(s[i]==r[i])
i++;
else
break;
}
int j = 0;
while(j < n) {
if(s[n-j-1]==r[n-j-1])
j++;
else
break;
}
int l_max = n - i - j; // values of l_max excluding the starting \
same values and ending same values;
int k_min = 1;
int ans = k_min*l_max;
vi equal_intervals;
int count = 0;
for(; i < n; i++) {
if(s[i]==r[i])
count++;
else
{
if(count>0)
equal_intervals.PB(count);
count = 0;
}
}
sort(equal_intervals.begin(), equal_intervals.end(), greater<int>());
for(int equal_iterval : equal_intervals) {
l_max -= equal_iterval;
k_min++;
// cout << k_min*l_max << '\n';
ans = min(ans, k_min*l_max);
}
cout << ans << '\n';
}
// Method 2: - > Traverse k from k = k_max till 1;
// while(t--) {
// string s,r; cin >> s >> r;
// int n = s.length();
// bool check = 0;
// int count_equal = 0;
// int k_max = 0;
// int l_min = 0;
// vi equal_values;
// for(int i=0; i<n; i++) {
// if(s[i]==r[i]) {
// if(check)
// count_equal++;
// }
// else {
// if(!check) {
// k_max++;
// check = 1;
// }
// l_min++;
// if(count_equal > 0) {
// equal_values.PB(count_equal);
// count_equal = 0;
// k_max++;
// }
// }
// }
// sort(equal_values.begin(), equal_values.end());
// int ans = k_max*l_min;
// for(int equ_val : equal_values) {
// l_min += equ_val;
// k_max -= 1;
// ans = min(ans, k_max*l_min);
// }
// cout << ans << '\n';
// }
return 0;
}
Guys this is best video for this tutuorial. Watch this
4 Likes
whats wrong with this code
#include <bits/stdc++.h>
using namespace std;
char s[1000000],r[1000000];
//bool bysort(pair<long long int,long long int> &a,pair<long long int,long long int> &b){
//}
int main() {
long long int t,i,count,sum,k,l,ans,n,k1,sum1,a,b;
scanf("%lli",&t);
while(tā){
vectorv;
scanf("%s",s);
scanf("%s",r);
count=0;
l=0;
k=0;
sum=0;
a=0;
b=0;
n=strlen(s);
for(i=0;i<n;i++){
if(s[i]!=r[i]){
if(count==0){
k++;
a=i+1;}
count++;
}
else{
sum=sum+count;
if(count>0){
if(k>1)
v.push_back(a-b-1);
b=a+count-1;
count=0;
}
}
}
if(s[i-1]!=r[i-1]){
sum=sum+count;
v.push_back(a-b-1);
b=a+count-1;
count=0;
}
sort(v.begin(),v.end());
l=k;
ans=ksum;
for(i=0;i<(l-1);i++){
sum=sum+v[i];
k=k-1;
ans=min(ans,ksum);
}
printf("%lli\n",(ans));
}
// your code goes here
return 0;
}
Yes obviously we can, but each bridging decreases k by 1 right? hence if we bridge together say 5 islands, its effectively reducing k by 4. hence we only bridge two consecutive islands for every decrease in k by 1.
1 Like
Ok, got it Thanks a lot for explaining 
Thankyou for all the observation. It was really helpful
got it thanks!
Great Editorial!
i am getting wrong answer can someone please debug it or provide me some testcases where it can give wrong answer.thanks.
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define endl ā\nā
#define pb push_back
#define mp make_pair
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(tā)
{
ll n,ans=0,i,k=0,kh=1,l;
string r,s;
cin>>s;
cin>>r;
n=s.length();
vectorv,v1;// vector v contains the indices where s[i]!=r[i]
// vector v1 contains the difference of adjacent element of vevtor v.
for(i=0;i<n;i++){
if(s[i]!=r[i]){
v.push_back(i);
k++;
}}
ll n1=v.size();
if(k==1)
cout<<ā1ā<<endl;
else{
l=k;
ans=kl;
//cout<<n1;
for(i=0;i<n1-1;i++){
v1.pb(v[i+1]-v[i]-1);
}
for(i=0;i<v1.size();i++){
ans=min(ans,(k-1)(l+v1[i]));
kā;
l=l+v1[i];
}
cout<<ans<<endl;}
}
return 0;
}
Help me find error in my logic - Each āislandā will either will be merged with the previous one or wonāt. For each island, I maintain a pair, which holds the total number of letters changed till (including ) that island, and the k values. Hence for every new island, the answer (k*l) for the two cases, i.e merged / unmerged, and go with the minimum.
Here is the code
1 Like
I am getting runtime(sigsegv) error on submission , but my code is running perfect for all test cases in my ide . Can Someone help me.
wow ! great explanation !! 
What to elaborate? Just do the other way around - start with a single segment (k = 1) that starts at the leftmost position of non-matching characters and ends at rightmost position of non-matching characters. Then remove the segments of equal characters in descending order of lengths. Each time you do this the number of contiguous segments (k) is incremented by 1, and the total length (l) decreases by the length of the removed segment.
I found this problem and its approach really interesting, can you share some similar sort of problems??
what is wrong in my code?
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--)
{
string s, r;
cin >> s >> r;
int n = s.length();
vector<int> gap;
int l = 0, k = 0, g = 0;
int flag = 1;
int gflag = 0;
int firstTime = 0;
for (int i = 0; i < n; ++i)
{
if (s[i] != r[i])
{
if (gflag)//making array of gaps
{
gap.push_back(g);
g = 0;
}
if (flag)//counting k
{
k++;
flag = 0;
}
l++;
gflag = 0;
firstTime = 1;
}
else
{
if (firstTime)//if starting is different no gap
{
g++;
gflag = 1;
firstTime = 1;
}
flag = 1;
}
}
int ans = k * l;
sort(gap.begin(),gap.end());
int kk = k;
for (int i = 0; i < kk - 1; ++i)
{
if(ans > (k-1)*(l+gap[i])){ //
k--;
l+= gap[i];
ans = k*l;
}
}
cout << ans << '\n';
}
return 0;
}
Please add comments in the code. Itās very difficult for beginners to understand without comments.
1 Like
Great editorial. This question took me longer than Iād like to admit.
To clarify on the Editorialistās solution:
The variable fst stores the length of each successive gap encountered during the pass. The bool badstuffGot is used to ignore the identical characters in the prefix part (if present).
For eg. if strings are aaababa and aaaaaaa , then the initial aaa shouldnāt be considered.
Due to the nature of the pass, we push in fst into our vector only when we encounter unequal characters. Hence, identical characters in the suffix part of string s, will not be considered, which is correct.
2 Likes
Beautiful and well explained editorial, thanks a lot!