Given a word, convert it into a palindrome with minimum addition of letters to it [closed]

Question

Here is a pretty interesting interview question:

Given a word, append the fewest number of letters to it to convert it into a palindrome.

For example, if "hello" is the string given, the result should be "hellolleh." If "coco" is given, the result should be "cococ."

One approach I can think of is to append the reverse of the string to the end of the original string, then try to eliminate the extra characters from the end. However, I can't figure out how to do this efficiently. Does anyone have any ideas?

Answer 1

Okay! Here's my second attempt.

The idea is that we want to find how many of the characters at the end of the string can be reused when appending the extra characters to complete the palindrome. In order to do this, we will use a modification of the KMP string matching algorithm. Using KMP, we search the original string for its reverse. Once we get to the very end of the string, we will have as much a match as possible between the reverse of the string and the original string that occurs at the end of the string. For example:

HELLO
    O

1010
 010

3202
 202

1001
1001

At this point, KMP normally would say "no match" unless the original string was a palindrome. However, since we currently know how much of the reverse of the string was matched, we can instead just figure out how many characters are still missing and then tack them on to the end of the string. In the first case, we're missing LLEH. In the second case, we're missing 1. In the third, we're missing 3. In the final case, we're not missing anything, since the initial string is a palindrome.

The runtime of this algorithm is the runtime of a standard KMP search plus the time required to reverse the string: O(n) + O(n) = O(n).

So now to argue correctness. This is going to require some effort. Consider the optimal answer:

   | original string | | extra characters |

Let's suppose that we are reading this backward from the end, which means that we'll read at least the reverse of the original string. Part of this reversed string extends backwards into the body of the original string itself. In fact, to minimize the number of characters added, this has to be the largest possible number of characters that ends back into the string itself. We can see this here:

   | original string | | extra characters |
           | overlap |

Now, what happens in our KMP step? Well, when looking for the reverse of the string inside itself, KMP will keep as long of a match as possible at all times as it works across the string. This means that when the KMP hits the end of the string, the matched portion it maintains will be the longest possible match, since KMP only moves the starting point of the candidate match forward on a failure. Consequently, we have this longest possible overlap, so we'll get the shortest possible number of characters required at the end.

I'm not 100% sure that this works, but it seems like this works in every case I can throw at it. The correctness proof seems reasonable, but it's a bit hand-wavy because the formal KMP-based proof would probably be a bit tricky.

Hope this helps!