How to convert a string to a palindrome with minimum number of character replacement such that palindromic string contains a given word?

Question

We have a string s, containing lower case alphabets (a-z). We can replace any character with any other character, and we can do this any number of times.

We can to make a palindrome string p from s, such that the p contains a given specific words(i.e. let's suppose linkedin ). Now, we need to find the lowest number of insertions which would take to convert string s to p.

ex - s = linkedininininin then the palindrom string p would be linkedinnideknil and the result would be 6.

second example( to make it more clear) - s = linkaeiouideknil then p = linkedinnideknil and result would be for 4, because we'll replace a with e, e with d, o and u with n.

I have tried to solve it by taking the LCS of s and p, and subtracting that from the length of s. but the problem is that how do I make sure that the palindrome is guaranteed to contain that given word(Linkedin)?

Please provide your approach. Thanks.

Answer 1

Assuming I understood your question correctly,

You can create the palindrome and then replace the wrong letters in s:

String s="linkaeiouideknil";
String p="";
String word="linkedin";
char[] wordC = word.toCharArray();
StringBuilder sb = new StringBuilder();
sb.append(word);
String drow = sb.reverse().toString();
sb.reverse();
sb.append(drow);
String pali=sb.toString();
char[] sC = s.toCharArray();
sC=Arrays.copyOf(sC, pali.length());
sb.delete(0, sb.length());
int counter=0;
for (int i = 0; i < sC.length; i++) {
    if(sC[i]!=pali.charAt(i)){
        sC[i]=pali.charAt(i);
        counter++;
    }
    sb.append(sC[i]);
}
System.out.println(counter);    
p=sb.toString();
System.out.println(p);

the output when run is 4.