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.

  • 1
    $\begingroup$ 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. $\endgroup$ – John L. Nov 1 '18 at 11:49
  • 1
    $\begingroup$ 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. $\endgroup$ – John L. Nov 1 '18 at 11:57
  • $\begingroup$ @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. $\endgroup$ – hsingla Nov 1 '18 at 19:24
  • $\begingroup$ @Apass.Jack I dont have the url, it was a not a publicly available test $\endgroup$ – hsingla Nov 2 '18 at 10:54
  • $\begingroup$ See also: Convert given string to Palindrome with given substring (including an example that confuses me). $\endgroup$ – greybeard 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.

The above description should be enough to set you up. You may want to improve it or look for better algorithms.

  • $\begingroup$ 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. $\endgroup$ – greybeard Apr 26 '20 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.