convert s1 to palindrome with s2 as its substring

Question

https://discuss.codechef.com/t/given-string-s1-and-s2-how-to-convert-given-string-s1-with-minimum-changes-to-palindrome-which-includes-s2-as-substring/69769

can some one help me understand this code please

#include<bits/stdc++.h>

using namespace std;

int main(){

string s1,s2;
cin>>s1>>s2;
int l1=s1.length(),l2=s2.length();
int ans=INT_MAX;
if(l2>l1){

    cout<<-1<<endl; // not possible
    return 0;
}
for(int i=0 ; i<l1-l2+1 ; i++){

    string temp=s1.substr(0,i)+s2+s1.substr(i+l2); // place s2 in all possible positions in s1
    int cost=0;
    // calculate cost to place s2
    for(int j=i ; j<i+l2 ; j++){

        if(s1[j]!=temp[j])
            cost++;
    }
    int z=0;
    // find the cost to convert new string to palindrome

Can someone explain below code please

    for(int j=0 ; j<ceil(l1/2.0) ; j++){

        if((j<i || j>=i+l2) && temp[j]!=temp[l1-j-1]) //(explain please) if s2 is in the first half of new string
            cost++;
        else if(temp[j]!=temp[l1-j-1] && (l1-j-1<i || l1-j-1>=i+l2)) // (explain please)if s2 is in the second half of new string
            cost++;
        else if(temp[j]!=temp[l1-j-1]){ // if s2 is in both halves

            z=1;
            break;
        }
    }
    if(z==0)
        ans=min(ans,cost);
}
if(ans==INT_MAX)
    cout<<-1<<endl;
else
    cout<<ans<<endl;
return 0;

}

Answer 1

Palindrome... same backwards as forwards... The first part of your code overlays s2 on top of characters in s1 starting at some position: i. the string temp is the first i characters of s1, then all of s2, then whatever characters remain in s1 that werent covered up. The length of temp should be the length of s1.

In the j loop, you are iterating on 0 to half the size of s1 rounding up.

Your first 'please explain' is looking to see if the index j in the string temp falls on a character that was part of s1 (whether before the s2 characters or after them). It also looks to see if the character in temp at index j matches its spot on the flip side (ie is that character and its mirror already equal as they would have to be in a palindrome). If is part of s1, but not a match, you have a cost.

Your second 'please explain' looks at the back half of the temp string... it looks to see if the character at the mirror position to j in the string temp falls on a character that was part of s1 and again looks to see if the character in that position matches its flip... if not, there's a cost.

You're basically looking at the characters in the temp string starting at the ends of the string and working towards the middle. So you look at the first character first. If the character is from s1, it can be switched to be whatever the last character is. So you just increment cost. Then you look at last character in temp. If it is from s1, then it can be switched to be whatever the first character is. So you just increment cost. Now increment j, so you're looking at 2nd char and 2nd to last char, increment j again you're looking at 3rd char and 3rd to last char. etc etc....

If at any point you cant swap the char at the front and you cant swap the char at the back.. then if they don't already match, its impossible to have a palindrome.