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.
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
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.
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;
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.
