Converting a word into palindrome

Q: Given a word, convert it into a palindrome with minimum addition of letters to it. letters can be added anywhere in the word. for eg if hello is given, result should be hellolleh.

Algorithm:

You need to find the longest palindrome at the end of the string. An algorithm to see if a string is a palindrome can be created by simply running one pointer from the start of the string and one from the end, checking that the characters they refer to are identical, until they meet in the middle. Try that with the full string. If that doesn't work, save the first character on a stack then see if the remaining characters form a palindrome. If that doesn't work, save the second character as well and check again from the third character onwards.

Eventually you'll end up with a series of saved characters and the remaining string which is a palindrome. Best case is if the original string was a palindrome in which case the stack will be empty. Worst case is one character left (a one-character string is automatically a palindrome) and all the others on the stack. The number of characters you need to add to the end of the original string is the number of characters on the stack. To actually make the palindrome, pop the characters off the stack one-by-one and put them at the start and the end of the palindromic string.