Given strings s1 and s2, consider the problem of converting s1 to a palindrome string p such that s2 is a substring of p,
where the only operation allowed on s1 is replacement of any character with any other character.
What is the minimum number of operations required for this task?
Here is a description of a simple brute force approach that works in $O(n^2)$, where $n$ is the length of $S_1$.
Let $m$ be the length of $S_2$. If $m>n$, return -1 immediately, indicating impossibility.
Keep a counter on how many characters will be changed. Change $S_1$ so that its substring with length m that starts at index 0 is the same as $S_2$. Mark the indexes where characters have been changed. Also chang $S_1$ so that ist substring that starts at index n-1-0 and goes backwards to index n-m-0 is $S_2$ backward. However, abort this try if we have to change the characters that has been marked. Now change the remaining characters of $S_1$ to make it a palindrome. That is, if the character at index $i$ is not same as the character at index $n-1-i$, change the later to be the former. Once done, the counter tells us how many changes is needed to make $S_1$ a palindrome that has $S_2$ as its substring starting at index 0.
Repeat the above with index 0 replaced with index $1, 2, \cdots, n-m$, keeping tracking of the minimal number of changes.
The above description should be enough to set you up. You may want to improve it or look for better algorithms.
