# 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. 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. 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. Nov 1 '18 at 19:24
• @Apass.Jack I dont have the url, it was a not a publicly available test Nov 2 '18 at 10:54
• See also: Convert given string to Palindrome with given substring (including an example that confuses me). Dec 27 '19 at 19:35

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.
• If any of the characters in $S_2$ occurs more than half its frequency in $S_1$, $S_2$ will have to straddle the middle of $S_1$. If additionally $2m < n$, $S_2$ can't be a prefix of the palindrome. Apr 26 '20 at 4:36