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

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

First make a function to test string for palindrome-ness, keeping in mind that "a" and "aa" are palindromes. They are palindromes, right???

If the input is a palindrome, return it (0 chars needed to be added) Loop from x[length] down to x[1] checking if the subset of the string x[i]..x[length] is a palindrome, to find the longest palindrome.

Take the substring from the input string before the longest palindrome, reversing it and adding it to the end should make the shortest palindrome via appending.

coco => c+oco => c+oco+c

mmmeep => mmmee+p => mmmee+p+eemmm