# Convert given string to Palindrome with given substring

Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other character. Find minimum number of operations required.

• Welcome to Computer Science! Your problem looks like interesting. If it comes from an online course or contest or article, please add a URL in the question using the "edit" link. If it comes from a book or a paper, a reference. Besides paying proper attribute to the original source, that information motivates and helps more people answer your question faster and better. – Apass.Jack Nov 1 '18 at 11:49
• What did you try? Where did you get stuck? We're happy to answer questions ("How does X work?" "How does Y relate to Z?") that will help you find the right or better approach, but you've just given us a bunch of orders ("Do A!" "Do B and C!"). We are expected to see a question that comes from you own thoughts. – Apass.Jack Nov 1 '18 at 11:57
• @Apass.Jack I saw this question in an interview test. Cant think of even a brute force approach. Anything you can think of, please do share. – hsingla Nov 1 '18 at 19:24
• @Apass.Jack I dont have the url, it was a not a publicly available test – hsingla Nov 2 '18 at 10:54

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.